(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
See other formats

Full text of "mit :: ai :: aim :: AIM-380"


Memo No. 3S0 

Sept I9TO 

' /. 

Forward R ea iO h iiij and [)epEndEncy*T)l retted B^ickr ratting 
In a System for GfrtHpiiLrr- Aided Circuit Anj)y;|$ 

by Richard M. Stallman and Gerald Jay Sussman 


We preiens a rule-based system For computer-aided Circuit analysis. The set of rules-, 
called EL, is written in a rule language called A5tS. Rules are implemented by ARS a* paltcrn- 
dlrtcted invocation demons monitoring an associative data ba*p, Deductions are performed in an 
antecedent manner, giving EL's analysis a catch-as-catch-can flavor suggestive of ihc behavior of 
expert circuit analyieis. We call this style of clr:uit analyse pfcyaga ilOij Of Constraints . The 
tystem threads deduced fait* with jurs-Lcf icatians which mention the antecedent facts and the rule 
used. TIiese justifications may be examined by the user He gain Insight into the operation of the 
hi of rules a* they apply to a problem. The same justifications are used by (be system to 
ditfrminE the currently naive database context far reasoning in hypothetical situatiunt They aie 
alio used, by thE system in the analysis failures, to reduce the search spate. This ka'ds to ef fecllve 
control of combinatorial search whkh we caH dependency-directed bach tracking - 

Work TEparned herein was conducted at ihr Artificial Intelligence Laboratory, a Massachusetts 
Institute of Technology research program jupporicd in part by the Advanced Research Project* 
Agency Of the DEpartment of Defense and monitored by the Office nf Naval Research under 
contract number NfJ0uH-7^c>C6t3. 

Hang popple contr ibuted tu this uork; A Men Broun, Orau 
ncDerJnot + + Johan da tfleer, Kurt Vanlehn, Louis Braicla* Richard 
Fik.ee* and Earl Sacerdoti gave ue some excellent Ideas* Guy 
Steele. Charles Rich and Ben Kuipers gave ue some important 
editorial help- Johh Allen. David ffarr\ Pat Winston and Paul 
Penfield also prnvirierl yund advice. 


Introduction 2 

AnaFysta by Propagation of Constraints 5 

Facts and Laws \ 1 

The Method of Assumed States l% 

Mak i ng Choice? ^G 

Dependencies and Contexts [g 

Contradictions 22 

Compound Devices ahd Identified Terminals 24 

The Queue-based Control Structure 27 

The Data Base of Facts and Demons 30 

Conclusions 33 

Append 1^: An Annotated Example 36 



Bibliography 55 

Ill traduction 

A major probhem confronting builders nf automatic problem-solving systems Is lhat of 
the Combinatorial explosion of" search-spaces. On* way to a ttlck this ptoble^vi is lo build system* 
that effectively use the result j of failures to reduce the search space -- that learn t rom their 
ejiploration of blind alleys, 01 '™ 1 ''*'' 1 Another way is lo represent the problems and rhelr solutions in 
such a way that combinatorial searches are self limiting 1 "™*" 1 

A second major problem IS the difficulty of debugging programs containing large 
amounts of knowledge. Tbe complexity of the interactions between the "chunks" of i. nowise 
makes It difficult to ascertain what it to blame when a bug manifests Itself , C€ "' p,, " 1y One approach 
to this problem is 10 build systems which remember and explain their tea soning. f rpll "* r,: Such 
programs are more convincing when right, and easier to debug when wrong. 

We have designed and lmplern*nted tlfip a problem-solving language railed AF$ APS in 
which problem-solving rulfs are represented as demons with multiple patterns of 
inVocation* 1 "*^"" 1 ^ iPW5 * l,nn monitoring an associative data base*' 1 hH,, It performs all 
deductions in an antecedent manner, threading Lhe deduced facts with justif tcaiions, which mention 
the antecedent facts used and the rule of inference Applied. These justifications may be examined 
by the user to gain insight Into the operation of the system of rules as they apply to a problem, 
The same Justifications are employed by the system to determine the currently active data -base 
context for reasoning in hypothetical situations Cfln, * 1(l Justifications- are also used in the analysis or 
blind alleys to extract mfmmalinn which will limit future seaich. 

We have used AES tn implement a set nf rules for electronic circuit analysis. This set of 
rules, a Version of EL, encodes familiar approximations to physical laws. sUch as Kircbof f's laws 
and Ohm's law as well as models for more complex devices such as transistors. Fads, which may 
be given or deduced, represent data such as the circuit lopology, device parameter*, and voltages 
and, currents The antecedent reasoning of ARS gives analysis by EL a "catch-as-catch-can* flavor 
suggestive of the behavior of a circuli expert. The justifications prepaied by ARS allow an EL 
user to examine the has Is nf lis concbliJon?, Thtt ll useful In understanding the operalion of the 
Circuit as welt as in debugging the £L rules. For example, a device parameter not mentioned in 
the derivation of a voltage value ha* no part In determining that value. If a user changei some 
part of the circuit specification (a device parameter nr an imposed voltage or current), only those 
facts depending on the changed fact need be "forgotten" and re deduced,, so small changes in the 
Circuit may need onlv a small amount of new analysis. Finally, the search -limiting combinatorial 
methods supplied by AR& lead to efficient analysis of circuits with pkcewise-iinrST models 

The application of a rule in ARS implements a one s»ep deduction . A few examples, of 
OTte-itep deductions, resulting from the application of some EL rules in the domain of resistive 
network analysis, are: 

I; If rhe voltage on one terminal of a voltage source is given, one can assign the voltage on the 

other terminal. 
% If the voltage on both terminals of a TesLstor are glven k and the resistance is known, then the 

current through it can be assigned. 
3; If the current through a resistor, and the voltage on one of its terminals, is known, along 

with the resistance or [he reilHOr, then the vollage on the crther terminal can be assigned, 
i !P a 1 - but one of the currents into a node aregJifen. the remaining current can He assigned. 

The style of analysis performed by EL, which We call the method of propagation of 
rf>ni||-ajnLs 1 ,,r< '" ,,|, * n rp^i.tu*s :h t n:rDdurLn- in I imrrpu^lur :5f rr^i? ^ y n ib- >l i :. qmntitir: 
Though the system has routines for Embolic al & ebra, s '' mfcdH ""f* 1 * 1 *' 1 they can Jimdk only linear 
relationships. Nonlinear device! such S.* transistors are repie^emed by piecewisc-linear models that, 
cannot be used symbolically; they can be applied only after one has gufl5,&ed* d, ' , " a particular 
operating region for each nonlinear devke in the drcukt. Trial and error can f trtd. the tight 
regions but thii meth od of assumed states, is potentially Combinalorially explosive. ARS applies. 
d ependen cy d i rected backtracking, a scheme which limits the search as follows: The system notes a 
contradiction when It attempLS (o solve an impossible algebraic relationship, or when discovers thai 
a transistors operating pnlm is not Within the possible range for dC-5 assumed region. The 
antecedents of the contradictory facts are scanned to find which nonlinear device state guesses 
(more generally, the backtrackable chokepoints) ire relevant; AR5 never Iries that combination of 
guesses agam. A Short lis! of relevant chotcepolnts eliminates from consideration a large number 
Of Combinations, of answers to all the crther {irrelevant) choices TbiS is how the justifications (or 
dependency records.) are used io extract and retain mote information horn each cu'iiraUicticn than 
a chronological backtracking system BKkl " ,<k,n * A chronological backtracking system would often 
have to cry many more combinations, each time waning much labor tediscoveriuT ihe original 

How It works; 

In EL all Circuit- specific knowledge Is represented! as assertions in a relational data bn,e. 
General knowledge about circuiis is represenlpd by [aws, whkh are demons subject to pattern- 
directed invocation Some laws represent knowledge as equalities. For example, there is one demon 
For Ohm's- law for TeslJlors h one demon that knows that the current going into one terminal of a 
resiitor must come out of !he other, one demon that knows that the currents on the wires coming 
Into a node must sum to letc, etc. Other laws, called Monitors handle knu-wlcdgc in the form of 
inequalities: For psample. I -MOfllTOR-DI DDE knows that a diode can have a forward currenr if 
and only if it is DH> and can never have a backward current. 

When an assertion (foj example, 1** CrTXTADE: 1D □! 1 I 3.4| , which says that the 
voltage on QT» collector has the value 3.+ volt*) u added 16 the data base, several demons will In 
general match it and be triggered . (In this example, they will include DC-KVL* which makes, jure 
that all Other elements* terminals connected to QJ's collector art also Vnown to have that voltage, 
and VCE-H0N1TDP-BJT, which checks that QJ IS COttectly biased for its assumed operating region ). 
The names of the Inggeted laws are put on a queue, together with atgumcnls such as the place Jn 
the Circuit Lb at Ehe law is To operate. Eventually they will be taken off the queue and prtKCtMd. 
perhaps making new deduclrons and starling the cycte over again 

When a law is finally processed, il can do two useful tlungs; make a new assertion (or 
several), or detect a contradiction A new assertion is entered in the data baw and hfci its 
antecedents recorded; they are the a sorting demon l(3elf. and all the assertions which invoked it or. 
Were used by It, ThfeS complete memory of hnw every datum was deduced becomes useful, when a 

contradiction U to b* handled A contradiction indicates thai some previously made- arbitrary 
choice (e.£, an assumption of the linear dp eratinj region of wms nonlinear component) was 
Incorrect. ARS warn backward along- the chains- of deduction Cram the scene of the contradiction, 
to find those chokes which r.&n1rlhuted to lhc contradiction, and records ihem all in a NDGOOO 
assertion to make sure thai the same combination « never tried again. INOCOOO ' lrTDti€ Ql J 
CUTOFF! C [HODE 051 DM) Hi a NDCODD a Hem™ that says that it cannot be simultaneously true 
that transistor Ql H cut off and diode D5 U ronducting. Such a MOGOCC might be deduced if Ql 
and D5 were connected in series. NeXI, one of the conspiring choices is arbitrarily tailed the 
"culprit" ("scape-goat" might be a. beirer term) arid rC-clici*en diFfefently. This is not mere 
undirected trial *nd error search as occurs when chronological barracking wllh a sequential 
control Structure is Used, since- it is guaranteed not to waste time trying alternative answers to an 
Irrelevant question. The HQGDQD assertion Is a further innovallnn rh-at sal/es evpn more 
computation by reducing the slie of the search space, since It contains not alt th-e choices in effect, 
but only thoje that were ipectfttaltj astd in deducing the tontradktion. Frequently some of the 
Circuit's transistors will not he mentioned at all. Then, IheNDOTCJ applies rega id less of the States 
ais-umed for those Irrelevant transistors. If theie am ten transistors in the circuit not mentioned In 
the MOGOOD, then since every transistor has three states (in the EL model) the single NDGOJQ has 
ruled out 3 W -S3049 different states of the whole circuit. 

Analvsb by Propagation of OiiSLraiiits 

Consider a. simple vrplla.ge divider: 



Suppose that chc voltage .ir she midpoint is known to be 3 vohs. relate to the indicated ground. 
Since there is known to be no DC current ibrnugh the capac itor, tt li possible io del ermine- the 
Hren|-[h of the voltage source, Forward reasoning is doing it Hnj way: First, use Ohm's, law lo 
compute the current through R 2 f ; t>m J"S resistance and the difference of (be voltages cm Its 
terminal!. NeJiT, the current through R^ can be i«n, via KCL, 10 be Ibe same a* that through Rj- 
Finally, that current, together with R.'s resistance and the vpltage at the midpoint, can be Fed Io 
Oh pi' J law TO produce the voltage at the top. This is an example oF what we call "forward 
reason ing* or {as. applied to circuits) "propagation of constraint". 

However, not all Circuit problems can he sailed so samply. Consider a. kadder network: 

Such A n«wort might be solved with tbm node equations or by series-parallel reduction, More in 
the ipint Of forward reasoning is "Cuiltemjn's Trick"; 

We assume a node voltage, e, al the end of the Ladder. Thli implies a cunem, e/5. goin£ 
down R^ by Ohm's Law. KCL then tells US that Ihis current must come mt of Re- But we tnow 
the voltage on the right oF ft^ and (he current though It. SO ure deduce that Lbe voltage nn iti leFt 
is 2e. We use this voh.age lo deduce Lbe current through R^ and then KCL to give- tis the current 
through Rj. We continue this process until we get all node voltages defined in term? Of e; 


But now we know 8e * |&, therefore e « bf4 volt We have s&lvcdt the network with I equation in 

Alii, GuillemLn's (rick Tails in the follcying circuit: 

At first glance, (his h a 3 node equation networt with no possible senei-paialtel reductions. We 
want to feneraliie GuiHemm's [tick to soke t h i-s network (wuh fewer than 3 equaucmO. 

We Ki.rsc a^ume a node po«ntia.l, e ( , at the top of J? & Thus, we deduce that the current 
through Rg is eJ4. At this point we can male no f urt her one-step deduct ions. Rather than givp 
up, let'i poke it again. We assume a node poten-jal. t^. at ih* [Dp of Rj. We can now conclude 
that the current throuf h K^ is e^l and the current through R 5 (nwajuted. to the right) n te^-e|)/2, 
Wir can no-w use KCL to deduce that the current (h rough R-p (to I he right) is (3e,-!?e->)^ and that 
the current through R^ n Oe^-eAf2- 




Al this point we can deduce thai the voltage on rhfi lef tmou terminal of R7 it ej+(3/4X5G|- 
2*9) Or (S3f|-6ej)/4. We can alw deduce that the voltage 00 the leftmost terminal of R3 is 

tj+fiHSej-e^y^J-L^-l^. Since rheje terminals are connected tog-Ether we have two repressions for 
trie same node voltage. Setting (hem equal and simplifying, w*get e|~2e>>- Tbe result of (hn 

sLmplLtKatLCMl ii; 


CoriCimnng h we dedluce that the current through Rj. must be 5rg,'IO-e^/2. By KCL. the 
current through R ( mun be 2e^. Ohm's law now gives, as ihe voHage at the let l of R x as I5e 2 . 5lJl 

this voltage ii set by the voltage source, io l&Cr,-^. We conclude thai e.^2: 

We have solved the network with only two unknown?. A* we approach a full graph 
network, rhis method degrades smoothly 10 be [he node fn«hod, bur usually it uses far fewer 

What have we b«n doing? 

A fundamental concept here is thacuf a one-step deduction . In the case of a resistivE 
network with 'voltag-f? and current source* there are only a few kinds of one-Step deductions 

I- T; ;he voltage on are terminal of a voltage source Is given, one tan assign the voltage 

on the Other terminal. 
2: tf the voltage on both terminals of a resistor are given, then the current through it 

can be assigned. 
3: !f the current through a. muter Ij given, and the voltage on one terminal is ftlven h 

then the voyage on the wher terminal can be assigned. 
4i If all but one of the currents into a nods are given, Lhe remaining current can be 


Another basic concept here i? that of a coincidence . A coincidence occurs when a one- 
Step deducnon is made which assigns a value to a nntwork variable which already hn-5 a value. 
We have seen several coincidences. 3n the laddET network example a one-Step deduction of type 3 
assigns the node voltage Se ro a node which is already at 10 volts. In the second example,, the node 
at che [op of Rr> was assigned two different node voltages by two one-step deduction.* of type ?, 
and the voltage J5e^ even though it Already was J-nown to be 30 voids. In each of these- cases [he 
coincident? resulted in the foi mutation of AH equatiuH between (he competing assignments. At the 
time of a coincidence, the resulting equation should be solved, if possible, Tor one of its unknowns 
in terms of the others. The circuit is [hen redrawn with that unknown eliminated- 

Thus, the basic propagation analysis algorithm is, rather iimule: 

Algorithm: Propagation of Cons-trajnts 

ChoDiefl cLarum node and assign it h ; potential of ft 
loop: IF [here ii a om-e-trejJ deduction available 
Choose a deduction and mate it. 

[]] IF the fasi action was ihu a^s-i^nmenf of 
a node potential, took for a type I. £ or J 
deduction involving 1hat node 
[3] TF the las', action aligned a current, 

look for i type 5 or i deduction Involving 
that branch. 
IF the dcduCLlnrv caused ■> coincidence TH£N 

IF theequalion implied by the coincidence U a 

Ignore the coincidence (and be 
reassured by th* fact that it checks. 1 !), 

EFROR- Votl did something wrong 

Solve for one unknown in terms 
of the others (or for a number, if 
there *tf no othm!), Eliminate 
that unknown throughout the circuit. 
Co to toojj. 
IF there it a node without a node potitnclah 

Choose such a node and assign It a new nude potential vanahlf 
Go to loop. 

All of the unknowns introduced by the aigof iihm aw sure to have had their values determined by 
the time rhe algorithm returns. 

Now t whai about choosing where to place unknowns? We want to get as much action as 
we tan out of each one- One measure of !h* simultaneity or the situation is. given by a count of 
the number at unknown naln: :r. , -t-r.i-: : U j ..iwn u-e*"""' 1 For ^.irp'f rnnsuler uur lad do 
3g?m, All nodes except the ground and the top of the vnJtage source are unknown. In The 
following tircur. each unknown node haj b«en annotated with the number of unknowns it is 
connected m. 

We can «* that the middle notle has. two unkncuvn neighbor* whilt ihe others have Drily one. If 
we place a node potential on the middle node, we can only deduce one current while- if we place it 
at either one of the 1 neighbor node* we will g« Lhe whole answer. The rule n to place Ihe rode 
potential at a node of minimum unknown neighbor ThiJ also has bearing on where to place the 
datum. In general. we ivant a node which u maximally «nrarcted to unknowns,. v> as to constrain 
them quickly. 

Fact* and Law* 

Analysis by propagation oF constraints is a form cF antecedent reasoning in whiLh n 
given, dosed set of questions (in this case., the volsagesand currents at all points in the network.) ■* 
to be answered. ARS provides a genial framework f o? ihe irnnlemenration of antecedent 
reasoning systems; we developed it to support the particular set of rules fot electrical analysis 
which we call EL. Like any programming language, ARS n best explained by showing how it can 
be used to implement an example. We will now display sample parts of EL, and lrow they 
implement parti oF the analysis method already described. 

To EL a circuit is. made 1 up of devices and nodes A device Is any of the components- oiip 
woulci normally thmk of as present in the circuit, such as resistors, capacitors h transistors, and 
voltage sources.. Each device has two or more terminals by which it is connected to she rest of the 
circuit But two device tei minalt are never connected diy-tttfy. instead, they are both connected to * 
common node ft hat is the sole purpose of nodes.). 

AR5 requires that all inowlege to be manipulated be represented as assettiOltS, and their 
manipulators, So be expressed as demons. EL thrrtuore deals with f aas that name the devices and 
nodes m the circuit, and state which terminals connect 10 which nodes A node or device is named 
by an [5-fl assertion, such as flS-A RL RESrSTIJH) or IJ3-A N56 NQfJEK The 15- A assertions 
serve several purposes. They control the matches of restricted variables and they enable EL 10 
find all the nodes in the circuit, which is necessary for deciding where to pot a symbolic unknown 
when one js needed. 

Most devices, have parameters:, for example,, a resistor bas a resistance and a transistor 
has. a polarity. These; parameter's; values, are retarded, if known, by facts like 
{- (RESISTANCE R1J 1008. B) t which says that R,'s resistance is lOOO Ohms. They do CKH have 
to be specified, and EL can he "bac* -driven* to deduce them if enough voltages and current are 
known. Art example of this use of EL to aid the choice of device parameters is given in the 

The connections of the circuit are described by assertions like tCOffltCT rf$4 1*1 R1H , 
each naming a single node and a single device terminal. These asser-inns Treed never be entered 
by an EL user h however, because we supply a special input format for conveniently defining 
devices and wring-' them up inrn circuits (see Appendix). 

Each type of device has conventional names for i'.s terminals. For example, a resistor's 
terminals are known as HI and tf2i a transistor's are called E, B and C The COTivenHon.il 
terminal names have to be used because ;hey are rbeones that the laws for the device know about. 
It would be easy to wire a resistor up by its A3 and "4 terminals., but the EL law embodying Ohm's 
Law would not know about them. 

The knowledge EL accumulates durinjj the analysis of a arcuit invnlves, mostly the 
Values of the voltage at or the current through particular device term ma is. They aTe represented 
by assertions such as (■ (VQLTADE rjiRDi 10.01, I iv ■.hIh-s of symbolic unknowns, when 
learned, arc stored in the forfrt i VALUE KI.5 l&n 4J ► 

Perhaps the simplest circuit rules are those, such as Ohm's law, which can be represented 
by algebraic equations. In AR5 such a law can Ik Written Very simply: 

(U IVCUAGE (#1 !?fi)) \>fU (- 1 VOLTAGE ^2 !?R]> !>vzt- 

U fCUflflENT (#1 !?RET !>!) 4- [RESISTANCE !?R) rrtESl I 
(EQUATEON '(*- n V2E p f&» flES [) R}| 

This IS the EL law thai- implements Ohm 1 * law. Like ah EL laws, it has an arbitrary 
name, a set oF slot! or antecedent patterns ro ton'rol Us in vocal inn. and a body which in ( hit case 
consists r>F an algebraic equation. The nam*, chosen by us for mnemonic significance. is DC-QHE1. 
ASAP indicates Its invocation priority, whith is normal, as it is for all laws that are Simply equations 
between circuit parameters. OC-Qtfl declares the local variables Vl, v?, j and RES 10 liold the 
two terminal voltages, the current, and the resistance value of the resistor. In addition. The type- 
restricted total variable R is used for the resistor about which the deduction will he made. The 
long hit beginning with (- (VOLTAGE . , . contains the demon's trige^ *tots . Then purpose is 
dual: Co provide parterns to direct the invocation or triggering; of the demon, and (0 gather the 
information needed in applying Ohm's law once The demon is invoked. 

The ARS antecedent reasoning mechanism will signal 0C-0E*1 whenever a fact is «seri«l 
tha,t matches my of DC-OhTs trigger slois DC-OHfl itself then automatically checks all of its trigger 
slots to see which onts ire instantiated and which ones are not. That information is passed to the 
function EQUATION, whose job is to deduce whatever it can Fiora the equation It is given. IE" on? 
or the terms In the equation {L vi. V2, and RES, in this ens*) is unknown, EQUATION can 
deduce it from the others, If all the terms are known, EQUATE DM cherts that they actually satisfy 
the equation, and iF any of (hem is an a Igebrajc expression involving symbolic variables. EQUATION 
can solve foi urtc of them. Whenever EQUATION asserts a conclusion, it automalinalh/ record* the 
instantiations of the trigger slots as the antecedents of the conclusion 

Notke the (! before the list of trigger slots in flC-OHM, That li the list of mandatory 
£|Mj , dF winch in rhis case there are none. Mandatary slats are jutf like trigger slots except that 
(he law is not processed unless ail oF them are Instantiated. OC-OEfl's slots are not mandatory, since 
iF any tingle one rs missing 0C-0W1 can accomplish something by deducing a value Tor it. 
Mandatory slots are useful when a law is contingent on some fact. For example, different laws 
appty to conducting Tr&fiilSTOrS and cut-off transiStOiS. EL represents the knowlege that a transistor 
is. cut off with an assertion such as 


Wnen a transistor is cut off, no current flows into any of Its terminals. One law, DC-TUT-CUTOFF- 
]C, enforces :he absence o[ :olletlor current: 

{EOJATEQN 'if. e.9 OEJ 

Thji law hag * mandatory sine rnjuiiring that the tran^stor in question be till off. If thfH is 
known, [he taw will be applied and wkll deduce I ha; the collector current is iwa. If that is. not 
known, the Ifhv will never be applied, Now Thai (he slot that detects a known value of the collector 
current ii not a mandatory slot, and. to only function ll to fflsA* Oitt thai Such a known value will 
be noticed tof the law and checked for consistency. 

TIli: Me] hod or AiMimfd States 

The propagation method can be extended <q any devices with laws that are inveTtible: if 
One terminal voltage QT CUtrenl is Ln fact fu<cd when others are given, then an a Igeh ra ie expression 
tor it In termi of those Others may be needed L(1 the course of propagation. Moreover, the 
expcCSSicm must be "tractable", m the Jeme that rhs (hunah tti mechanical) algebraic manipulation 
system may need, to subsnruif m ir, iirriphf y H. or even solve tt for Unknowns appearing in it r in 
order to carry out The solution For example, handling a diode is loo tompticalcd, since Lt would: 
create the nea-d to solve eKpOlientlal equations. But even ah "ideal dLode" - a piece wise-linear 
approximation to a real diode ■ is too complicated to be handled symbolically as fluenlty as is 
necessary. It would introduce conditionals and "nunc* and H min H functions into the ess press Jon s t and 
they are not trivertible. 

But if the algebraic manipulation technology can 7 t handle the device's laws as .\ whole, 
stronger methods Of reasoning tan break them down. Electrical engineering hai a method Inoivn 
as the "method of assumed state* "^ which is applicable io pieteMrise-lincar devices such as ideal 
diodes. It involve* mating an assumption about which linear legion the device is operating in (for 
a diode, whether it is "on" or "off"). This makei iht Lund mortals siropltf y away, leading tractabk 
algebraic expressions to which propagation of Constraints applies. Afterwards, it is necessary to 
Cheek that the assumed states are consistent with the voltages and currents that have been 

For An example Of ilich icasoning, consider the diode and resistor in series: Assuming 

the diode to be noncondliC'lllg. we fcOtlld deduce that there is tero current Flowing, and that the 
voltage at the midpoint equate e. Since c is positive, that contradicts the conditions necessary Tor 
the diode to be Off. a* we assumed. On the other hand, if we assume that the diode is conducting, 
we deduce that the voltage ar rhc midpoint 15 zero, and tan then determine Ihe amount or current. 
The current is flowing downward through the resistor and diode, which is consilient wiih the 
assumption that the diode is conducting. 

When this method ii mechaniied h Lt iS heCeSsAry to cycle through all of the possible stair--, 
(linear regions) of the devjce h testing each one for consistency *ith the voyages and currents that 
follow- from it. When there are ievera] wrnpl l<a tttl devtCH, it 14 necessity Lo consider nil 
combinations of all different states for each device. This causes an exponential exploF.1011 of the 
number of states of the system that must be investigated. 

fW example,, thu circuit 

has three transiitors. If Che tTanE-is-tor model adniti three slates, active, cutoff and saturated., I hen 
(here are, a< first glance, 3^3^3 or 07 dLffcreni triples of Haws ihat must be considered, of which 
on I y erne (all three transjnors active) ii wit" tonsi went. But actually, the states of the fransiitors are 
completely independent; the itag-fj are coupled only fpr AC .^glials, and have no eFfec', an each 
other's bias conditions, Knowing thij, we can ftnrJ the corred itate fni each transisior separately, 
giving only 3*3*3 or 9 aimtinptjons to be Tested. Such Jkumions an? very frequent, and their 
detection is an effective way of reducing the w^rk entailed fry th<? <omomatortal search for the 
correct .states. 

Making' Chokes 

Using the method of uaunwa **« ™q«ir» the ability to rule choices, and to handle 
contradictions by m .kin« new ****>■ ^abilities .re bulk into ARS, to the conditions for 
lh* detection of > contradiction are a matter of i*p*rt ekemcal tnowlege, coined >" ^ law* 
A « equation law detects . contradiction If it *« that the equation II not satisfied be the known 

values of the quantities in it. 

However, Lhe method Of assumed statM carries, mother sort of knowkge. Of the 
boundaries of the differed operating region, of puaune-tLnciT devices. EL Ha. tpeciil laws 
knowr a5 monitor lews which check that a device is ,n fact in » cnnrcnmtnt consent wnh the 
state assumed for it The cond.t.onj ud b| monitor h« areoficn in«<| L «l.ti«. which .r.Mt « 
conducive to *ymM.e ^nipulFiMon as equate. AIM* qntolk »**« rauiinw are helpless 
With them. SO monitor tows cant do their job unbi numeral values are known for all the 
nara.me[eri entering mtfl the inequality 

When the operating region of a nonlinear de.ke is known, ttel knowledge ^ represented 
b f .DE3a«!a»™««.r. i ffleh»(DErEBHlKEJ ChODE 01> CUTOFF) . The£«lfw»li 
[ETEm»5~frfte«ri by the >est,on\ followed oy the 'answer* S«h knowledge might hive 
been deuced < lU ch as when wefirit learn that a transistor's emitter ^r«nl It Hit,,*nd then 
deduce tna: it mmi be cut of rfc or it might be the mult of an arbilmry choke. In the atter case, 
the chnke artf L 5 reprinted by a s.mllar CHOKE asserts ^CWICE inOOE 01 ) CUTOFF) , 
from whtrh we pretend that the QETEHMENED atsertk-n mi -deduced". The reason for hav.ng the 
two different assertions M thai all the Lransiaor laws that depmd on tine transistor s scale can look 
for the DETERMINED, ind thui work no inalter i«n» the kno*m State w a s arrived at, while the 
backtracking mechanism an look for the CHOICE, and avoid trying to^se other answer, for . 
question whose answer as not in doubt. 

In fact for the sate of el fideray, * nave lumped logetheir the state oondit.ons not by 
state but by the circuit variable they test. Her. is the monitor that checks transistors collector 
cur refits tor consistency ¥<iLh whatever State is assumed. 

U- ICURFflJNT (C !?HN *>1C> (- flE-DROP »mi !>BE-0RDFJI 
ICQNP [(APPflOK IC 9-91 

IU t«* IC BE-DRfJPl a, 8) ICWTHWICTIOW OEnDM aniecedehis 01 > 

It ii called a riDMJTOR^AU totead of jUil a LftU to that it will insist on having mim**l«l values 
for the local variables declared to need them, IC {the alitor current) and BE-MDP (whose „gn 
indicates the clarity of the AmMo* A ieroculkctOf current « coniLSteni with only on, Stmte. 
CUTOFF The fttnfltlan 09SERVE reports a mnl.adia.on id ARS if th« uansistor Is in any other 
state. In addition. « a timesa^mg nttasure, -f the transistor's itate has not at the moment been 
chosen OBSERVE choosei CUfGFF sance it is the only consistent choke If 1 C and BE-MQP have 

Opposite signs, th^ cotl«ICf current ii flowing b&ck*aids thraugh the rraniuiOi. which is 

impossible in anf sts te; in thar «s« r a contradiction u rfpfrrted 10 ARS far processing OrhciwJw, 

fhere is a phyilcally poi*i"ble, norritero collector ctirrenr, which is. consistent with any itnte w*^f 

CUTOFF. The function fcSSERr-NDGDOO reports (hat to A R&, (ius-ing a contradiction if an 

assumption of CUTOFF Li current!/ in force. If not, a NOGGOD assertion is created (i« 

Coin rAd id ions, below) io that fuiurc search through (he Space of slate-comb mat ions will be 


Dependent Lei and Contents 

The method of assumed stales requires that ARS be able tn reason From hypothetical 
assumptions. In addition, tnteHigew processing of CCmtTad ictions involves distinguishing the guilty 
assumptions from the Innocent ones, ARS's dependency records play a central role in both 

AR5 beeps complete record i of every deduction that it makes. The premises of the 
deduction can be found from che conclusion, and the conclusion from the premises. These records 
ire used, by ARS for several purposes- explaining' the derivation of a fact lo Lhe user, finding ihe 
chokes, relevant to a contradiction, and delineation those facts which are amernly believed (O he 
True, A fact li believed (:n) if it has well-founded support from atomic assumptions "*hicli a if 
currently believed. An assumption, such as an artkibmrf choice of a device operating region, may 
becone disbelieved, perhaps because of a contradiction involving it. A fact which does not have 
well-foiinded support from believed assumption.': is said to be f^f Sf a choice {and lis 
consequence's) which has been oijfed returns to ravnr, we use the dependency information to save 
the effort of :ehl venting implications from scratch. This process is called uncmfing At any time, 
Eho« fact* actually believed arc said to be/X while those under a cloud are pur Dependency 
information lemalns forever, even as the facts involved rise or fall in favor. 

Here 14 a picture of the Contents of an ARS fact data base, containing several atomic 
facts -(device-stare choices, or Circuit construction Sped Fical Ions) and sundry consequences dF them, 
showing- a particular contest ^elected Al. Dl n r- 1 1 CI 4re aiOriliC data that are currently in. Suppose 
Aland A2 are device-sjate assumptions, and tn fact are alternative assumptions about the same 
device, so when Al is tn r A2 must beam, 

If A I vrere to be retracted, the fact, garbage collector would b* mvckrd, leaving the data tone as 

/ \ 

Believing A? iflHMd of A] woulci cause unewfing of MVtjal con sequences: 

In addition, deduction would have the chance to add mart Tacts: 

It may happen :Uw a fact can be seduced m more than on* way, ff one is certain of 
One's- premises, Extra proofs, of a known fact tan be discarded. When the premises ran be arbitrary 
Choices thai might be taken back, extra proofs are in porta nt, because they might remain valid 
When the premises' oF the original pronf are not. A I Though a program might be guaranteed to find 
the second proof again if the Firtl were invalidated, 'hat would waste time. Therefore, ARS keeps- 
separate records of each way that it finds to deduce a Facl. When two Facts imply each other {wnli 
appropriate other premises) it may happen thai AR5- tecofds a deduction of the f irut from the 
second and also a deduction of [he second i ram the first At First we were shocked by this, but it is 
inescapable, because with one set oF choices in effect it may be necessary to deduce Ihe first via the 
Second, while with other choices the second may be accessible only via the first. However, such 
loops in the dependency chains r .'fares a problem for processes such as contradiction processing 
which must trace out the remans I'm a Fact Lt is soluble-, however, because iF any fact that is rn 
ha* (as we would hop**) a valid reason- for brine, believed, Lt must be the apes of a non-IOuping 
subgraph reaching down to atomic assumptions such at Ihe wiling of rhe circuit and iJence-&rjr»> 
choices. For every one of the- facr* that is CWiently in., ARS singles out one of the ways it was 
deduced as- its support, and those marled deductions are chosen to form a subgraph that contains. 
no loops. Back ward tracing df the dependency records then follows only the supports, and 
therefore always terminates. The selection of the supports is a by-product of the process used to 
determine which facts are sflll to be believed when an atomic assumption is taken hack., which 
Operates by tcannmsj forward from the atomic assumpticms currently believed and marking all 
their consequences AS a garbage collector Would. The facts that are marked become in, and the 
garbage facts are ami. 

Because facts and dependency infarn?Lion *re never totally foigOlten even wli?n «hey 
ar* disbelieved, a short cut is possible when a once heaved but laser invalidated fact is vahdair-rl 
once more. Ln a process known as uhfltfflng all the old consequents of the vindicated fact are un- 
examined, and if their other antecedents are all currently believed they too are marked in. If not 
for unoafing, those consequences, would be rededuced eventually anyway bj the laws that originally 
deduced rhciTi, but unending i:- much Pasttr- 

Taken tog ei her, Che ^wo processes of pace jmg' and unoinfing can be viewed as COtuext- 
jwnching between comers ench associated with some subset of the set of possible assumptions, 
Sjnce there are so many contexts to vjsit t the fatr* are not marled with the- name* of the (onre^tr 
they are in; ins.tea.dL, context switching musx identify and mark the facts that are in the context 
being entered. These contexts form a tang-led hierarchy instead of the usual tree. Entering a 
jubtontexc Ji beljeving an additional as.sump.ion. which is done by unCNJing together with normal 
deduction. M oving to a higher context is disbelieving some assumption; this is done, by means of 
the fact garbage-eolleetoT, when contradictions happpn. Note that, as in Ccnnivcr. a "subcontexi" 
generally contains mart assertion*, and a "iu percenter" contains fewer. 

In face, one could imagine the entire set of contexts a* eKHUng initially, but with no 
knowledge in any of them save the initial assumptions; then reasoning happens, adding more 
know ledge which is automat Ically placed m fbe con t^t.^ determined by the premises of each 
deduction. Contests in which contradictions are believed are the ones ruled out as acceptable 
solutions to she problem. The others are fertile ground for extension of knowledge. This point uf 
view raises one above the petty detail! of when one should b-acktracV (try working a cliff eieilt 
context}, and also raises the possibility of switching contexts simply because they appear unfruitful. 
and not necessarily contradictory (but. Shu has not been implemented). Also, since backtracking- is 
rust a change of the point of attack, Jt loses no information. 

A fact does, not itself belong 10 any context, although U may be known in a particular 
context, ar in several conletfli foi mdependen-t reasons The dependency records alio do not belong 
specifically to the context that was in effect when lhe deduction was made. Because of that,, they 
are always- ready to pull ibe consequence? imo a new context if the antecedents are deduced in it. 
Although a fact deduced ii certainly in (he currently selected corned, it may also automatically, by 
virtue of in dependency links, be in somesupenccntext of it (and also many sibling contexts), if us 
proof cud not make essential use of all of the atomic facts that define *he currently selected context 
In other words, a fact when deduced is not Simply "installed" in lhe currently selected con tear, the 
way it would be in Connive*; It goes (i ulcmtfta 'If into the highest supercontexts Ihat Its 
derivation will worl in, and is merely "inheilied" by the selected context. 

This context mechanism might be applied LO the understanding of processes thai develop 
over time by associating a unique atomic datum with each significant local event occurring in the 
process There would then be, for each slage of Che process, a contest in which lhe stale of lhe 
system at that stage was itnown. However, the understanding of the process would no* Lie tied to 
any global "time coordinate" and would not require any spurious time-ordering between events that 
were not causally related. Any "spaceuke hypersurface." slicihg through lhe process ■vnuH have a 
corresponding context; time would be a decentralized ob^ct Ihat could be advanced locally in one 
region of the process while being "left at the same instant' In whet regions- 


When EL uses rhe method of assumed states to analyze circuus containing nonlinear 
devices, incorrect assumptions are detected by means of 9 contradiction, which is the spec irk event 
in which the chosen assumptions are seen be inconsistent. A CW1C1 a diction is detected by a 
particular law - mast often by mohttnr tews thai tmitl for just that purpose. Contradictions art 
remembered both by contradiction assertions which are plaoncl in the dependency-structure- at the 
point Of contradiction, and by NPEO OO asserti on? which record essentially the same informal ion in a 
form easily used by the routines which choose alternate Slate- assumption* A contradiction 
assertion dCni!S not explicitly contain any mfotmaticm; its significance lies entirely in its list of 
antecedents. A NOGEap aswniun explicitly lists the state assumptions thai conspired to produce !he 
contradiction. A [ypkal contradiction might depend on doiens of atomic facts, including .some 
device-state choices such as 1 CHOICE IffiME 03) BtTA-rNFIMIEt and tCHDfCE [MODE 02 1 
OFF) . ai w c || as man y circuit construction details such as IflESJ STANCE Ri iefw, 31 and 
[CONNECT N54 <B qi | > , The contradiction action would have all of them as antecedent!; 
(indirectly); the NDGOUD assertion might be f NO GOOD I [nrjUE Q3) BETA-lNFtNITEJ t (HGOE 05"f 
OFFH, and Its antecedents would include the RESISTANCE and CONNECT assertions but not the 

When we view jets of assumptions as determining cnincxrs. a contradiction is a fact 
deduced in a specific contest, which shows that contest {and all of its sutamfexn) to be of no 
further interest. But if th« fact of the existence- of ihe contradiction is to be a ratable for use 
(such as in cofuroHLng a search), that fact must reside in a dif feieni coine.st. MQGDDC1 asserting fill 
thac fate. The simplest way to remember the contiadicuWs existence would be to assert a fact 
CtmtaiiHiJg a list of all of the atomic assumptions of the Contradicted comeKt. found by waging 
back through the dependency tree from the contradictory facts (or. just as good, from the 
contradiction assertion). In the example we are using, the BESJ STANCE the CONt^CT. and both 
CHOICES would be listed in the NKOOD, which would have no antecedents. Since such a NOGOPD 
won hi be true rega rd less, of the truth of any of the premises it listed, it would exist in the highest 
contest of all, which is the one that depends upon no atomic f ac^s. However,, (not {A and fl)) can 
also be Stated as {A implies (not B». Any subset of :he basis of the contradiction can be de- 
cmphasj;*d by being mad* antecedents of the NODQDQ rather than part of its list, In OUr original 
example, the RESISTANCE and CONNECT assertions were de-emphasized Denemphasis makes the 
information totally uti available m some con texts (those that do not include the de-emphasized 
antecedents), but by the same token Jtduces the number of N0G0QD* that are in at any moment, and 
also reduces the sue Of each NaDQrjO , » list. That is valuable, since whenever AR5 needs to Choose a 
state for a device it must ex amine ail HOCQODs thai are in, to eliminate choices already known to be 
incorrect; each NQGOOD must be processed to see whether it lists the choice under consideration, and 
Whether the Other atomic facts it lists are currently also in. De-empha$|zing some of the atomic 
facts causes the normal context mechanism m help with this filtering of the WQGOQD assert ion s. 

Of course, de-emphasis can have drawbacks. The mojr extreme possible de-emphasis 
would leave only one assertion In the NDGOOD's list, while all the others became antecedent of the 
NfJGOOD. This would male the NDGOOO almost useless for punting out contests which were not 
worth visiting. Imagine that Al, HI and ci are atomic facts that leari id a cnntiadlction. and that 

Al 15 listed as no good, with El and CI as conditions. If later Al ami Bl were in, and CI were 
under consideration for bditf, [hat NOGTOO asser tion would beeut, and there would be no 
understanding that Ci fed tea context already tried and discarded. The hOcarjD would not be 
performing its intended Function. This, would not be a disaster, JL nce bringing CI <* would bring 
bark the origin^ contradiction assertion also by urumrint;. but much time might be wasted This 
'thrashing" « most painful with such excessive de-emphasis, but any de-emphasis has I he ability to 
cause thrashing ,f its implicit assumptions about the relative stability of the atomic (sets prove to 
be wrong. 

A practical system must find a compromise between throning, and examining too many 
too-big NOGDCOi whenever a choice is made. We do nnt know of any domain-independent solution 
10 the problem. What is dear j* that it is good to dremphasize facts that are unlikely to change. 
Jn the domain- of electronic jiniklysis. we emphasise devfce-jtiti chokes, and de-emphasiie circuit 
wirtng and intrinsic device parameters such as the resistance *a1ircj of resistors, since during the 
analysis of a specific Circuit the latter usually do not change. In circuit design there might be 
occasions when some circuit vokages that repress the design criteria would be least likely to 
change, device-state assumptions would be guessed at next (along with approximate circuit wiring), 
and placement and values oF resistors and capacitors would be chosen last. Then, WDGOOD 
assertions might emphasize the defied wiring decisions and de-emphasitt the large-Kate Ones. A 
secon-d Wei of WGODQ assertions might speak of overall circuit plans, de- emphasizing only the 
design criteria. Thus., the level of a contradicted contest in the ranged hierarchy would guide the 
choice of a context for the WOGOaD. 

Compound Devices, and Idemif icd Terminals 

Engineers often thin* of a subcirciut 35. a "black box". A duly IjfcACfc, hov -■■ one whose 
insides are hidden h such as an op-amp -■ li intellectually (and computationally) just an element. 
More interesting is a "grey box" which may b* ambivalently Thought of as a black bos or as a 
configuration of component. Grey bo* es a re often used to sumroariie some aspect of the 
behavior of a configuration a; a whole. \{ ii economical (0 Store the most important features of 
the bchavLor of common cortf igujanons as grey 00* laws io that they Cio not have to be computed 
from scratch each time the Configuration is used. Sometimes, in tact, there arc laws about I he 
behavior Of a £unfi£UTaLicm which ace Crucial to analysis of circuits containing ii, but which air 
very difficult EC derive frcsni the behaviors of its components. 

For example, some common configurations of transistors cannot be understood ir> term* 
of EL's simple-minded model of transistors. Such an application is the emltter-couplcd-palr 1ECFJ: 



\ — 1 



The problem here js that one miHt use the exponential diode model of the transistors to derive the 
fact that (in a correctly b^sert ECP) the incremental difference In collector current? »s proportion^ 
to the difference in incremental base voltages (and furthermore, that constant of proportionality is 
almost Independent of the tiantlyoi' chHracte.nst<cs3. lw "* lrtin WecouW try to soke this problem by 
attempting to include the espon-ennal dtnde model of i he transistor and ^he algebraic expertj.se 
required to use it. Notice, however, that this important, but difficult to derive fact about the 
currents in an ECP Is in itself a simple linear law for the ECP. Grey-box laws allow us "package" 
this fact about ihe configuration so that It can be u*rd in analysis, without increasing the 

complexity of our basic transistor model. In N.- *a r we can use :he much S-irtlpler (but less 
accurate) models 111 r^uJt cases and have a way to impose the constraint? on the configuration! that 
d*pend on (he more ate uiace models. 

Another problem ll that there is not JJUSt one ECP Circuit. For example, here Is another 
variety of ECP: 

If wb had tq specify a distinct set of grey-bos laws to cover each instance of ECP we would be 
fighting 3. losing battle, We must express the laws to capture the essence of ECP and OCA any 
particular circuit 

The notion of a gtey box is implemented by the EL macro-device feature. An EL user 
may specify Lhat a particular subclrcuit Is to be viewed as a gsey bosi. EL has the ability to 
Identify a pornon of a Cncuit with a macro-device Cm a terminahbyterminal basis. The subcimut 
and the macro-device are re^rded as al!c:nate description* of what is connected to (heir common 
environment. The terminals of the matro-dtvicn- are each identified with a terminal of one of ilif 
device in the subcircuit. The device is allowed tn have unidentified connections, anri so is I he 
subclrcuit - in fact, to speak of the siibcirruit is slightly rnuleading r since it suggest? that (here rnUFt 
be a boundary surface that dividei the circuit into "inside" and "outside", and no such I* required. 
When two terminals are identified, EL assumes that they must have the same voltage and tkt jtiwf 
currfnt. This is not the same as connecting terminals at a node 1 

The macro-device is then juit a method of attaching- extra laws which supply additional 
constraints among the voltages and currenls Oft the identified terminals and thus help determine 
the CErcuit unknowns. Since whatever IS learned about a terminal of the macro-device is 
automatically propagated to the identified, lamina I of the subcireuit. the two sets of laws can 
stimulate each other If they disagree on their conclusions, a contradiction occurs. 

When a macro-devac.^ such as ECP. models some aspect of a configuration of device* 
with nonlinear properties, the special laws of the macro-device may be contingent on the ojwaMng 
regions Of iti Components. It j? also often true that Ihe whole configure ion bai fewer consistent 
states than one would calculate from the those of the parts taten independently, Furiheimtrre, as 

In the case of the ECP, thee may 110t bf arV f assignment of regions (using- the simple transistor 
model) [q the components which is consistent wirh lhe known behavior of the configuration. 

Thus- set of problems a resolved by allowing a macro-device ro have a set of opening 
regions of its own, on which ui own taws are com indent. Furthermore, (he Enacto-device must be 
able CO Cunlroi Ihe assignment af operating regions to its components. Thus, far example, An ECP 
may be either ^active" or "pinned" (PjUned means I hat otic Iransislcr is. either saturated or Cutoff 
whereas active means rh-P t both translator* Hill have icom to ma neu vtr,}. If ihe ECP is panned, 
the normal lawi or transistors apply, except 1bat we know ihat both transistors cannot both be 
active, If the ECP is active, then both iiansisrcns in it are assigned the special region "ecp-active", 
suspending the normal laws Ten transistors and providing a set <rf laws for this special situation 
In the ECP case, the active state is further broien down mto *wo subcases ■- it is eilber "balanced" 
or "unbalanced". The ECP ts assumed to be balanced, but then if the Test of (be circuit 
unbalances it, ihe balancing constraint u dropped These rules are embedded as special laws Tor 
the ECP 

Although EL can identify a specified par* of a circuit with a device of a specified type, 
U does, not have the ability to associate a macrcrrJevice type with a generic equivalent circuit, inch 
an Ability would) make possible the !wo operations of recognition of the occurrence of such macro 
devices as emmer-COuplcd-pairs or complementary pairs, without "hints" from the user, and 
iXpan-lien Of a macro-device mtoi an identified equivalent circuit. The latter operation migbt 
facilitate the use of an EL like sunpiogTam by * circuit-design program (either entirely automatic, 
or merely assisting a human). In addition, it might be applied to devices such as transistors, which 
are not "reaLly" macro-devices, but which an equivalent circuit might at times allow EL to model 
more accurately. 

However, such operations are more complicated than they seem. An equivalent circuit 
recognizer that would accept only a specific exact pattern of circuitry would to* of very littte use. 
Tbis is because the "circuit" of such an application as the ECP is so unconstrained; there can be 
many different arrangement of componenU in between the two ttanslstorj, that will have slight but 
useful effect* zm rhe behavior of the ctrant without making it useless, to vlewtitltt 1 configuration as 
an ECP. Tii us, the recognizer must be able to be flexible in its criteria The expansion operation 
is even more problematical, for while the recngnlier can a«ept many cnailt configurations, the 
ex pander must choose one appropriately, or give the user the abjljty to specify changes in almost 
all the details Of its expansion. But mating the user specify loo many details would deprive the 
expansion operation of its usefulness. 

The Quenched Control Strjicmre 

Tba gross-scale control structure used in ARS is event-triggered, as in a production 
system or a M» T kov algorithm, rather than scqinmual at in a classical programming language. 

Sequential control structure is confined 10 the inside of a law or demon; demons cannot transfer 
control to other demons, out only return to ihe scheduler, which has queues nf d™ns in :l in *ncl 
arguments to feed them. Drons can affect [he future actions of the program only |> r adding to 
Che queues, but even that is net done directly. Instead, demons auf rt and the process oF assertlun 
Enqueues demon? whose trigger-patterns match the newly justed f«t. This produces a degww of 
isolation for each individual demon, automatically making most device-law demons veiy modular. 
Tt also obviates a o-,. si t>:3 | flf decision-making thai would Olhcuvisr have toga into the Sequential 
algorithm for handling many local cinrait configurations. Circuit analysis must deal with many 
different types of bui Icing blocks, strung toother in any order. Without ibe queue, the overall 
st future of the deduction process would be thar of a loop containing a jingle man r way dispatch 
that decided what type of deduction was appropriate to perform next. 

There are actually several queues for demon -invocations, with different priorities, Each 
demon specif lps which queue it should goon There are three queues used for DC analysis Most 
demon s, including equation-laws, are intended primarily for deducing new facts. They go on the 
middle priority or normal queue. Monitor demons, which exist mainly For finding com radicr ions, 
go on the high priority queue That IS because .f there is no contradiction then all the demon* will 
be executed eventually anyway, so their order make* no difference; if there ji a contradiction, 
then the fastei it is found, the Jess time it wastes. The low priority queue is used for choosing 
device-state assumption^ because it is best to captor* all | he consignees oF one AHHffl|ilion before 
making man assumption*, m case there is a contradiction. Moreover, the possible states for a 
device can sometimes be narrowed down by knowledge about the devices environment Given the 
opportunity 10 try deduction t* to assume i device's state, it is better to make the deduction first, 
since they must both be done eventually, and the deduction has a ctonce of reducing the anwunt 
Of Wort involved in finding the correct device-state if the deductron 15. done first. 

There are three more queues for AC analysis, with lower priority lhan the PC queues. 
That is because the EL laws make it is rery unlikely for a contradiction to involve any oF the AC 
analysis; If the DC analyst finds none, there piobably is none. Agam, it pays to avoid doing any 
AC analysis for stares that are going to be ruled out anyway. 

Unfortunately, the queues of ARS are a very sensitive data structure. IF any demon that 
in fact ought to be run is missing from the queue, nothing will ever detect that fact, or put it batf. 
on the queue, since mat could be done only by the assertion of the fact that can (rigger the demon, 
and said Fact Is already asserted. Such problems are not bard to avoid when only straightforward 
propagation is involved The real difficulties come with contradictions. They are oF two kinds: 
those accompanying the forgetting or curing of facts, and those that pertain to the very demons 
which detect the contradictions. 

When a demon m AR& detects a contradiction, it drops what it was doing and makes a 
contradiction-assertion instead, causing the contradiction to be processed immediately. In some 
casei, that is guaranteed to cause the wring of at least one of the facts on which the demon's, 
operation depended. Such cases are non-problematical, if {as is usually the case) the demon will be 

incapable of doing; any useful work until a similar fact is later averted, and such an as.sertiun wilj 
enqueue (he demon Lrv the normal manner However, not all demons have that useful property. A 
case in point Ji that of the monitor demon It-nOMi^rjfl-Sjr, which examine* The em liter currents 
of all transistors. IT the emitter current is ?.em and the transistor is currently assumed To be active, 
the monitor detects a contradiction, ]f there u no assumpiion in forte a; the moment about the 
transistor'* state, the demon averts ;hst !he tiansistpr is cut off. Thus, if the demon is run because 
the emitter current has just been asserted to he zero, and a contradiction is delected, the demon 
really ought to be run again so it can make "cut olf ' ihc- new state. To mafce (hat happen, the 
demon explicitly requeue* itself. 

Most law* ate Simply equations fetohng Circuit paiameteis (Ohm's law is an example} 
The normal case Jn which such a law can do useful work is when all but one of the parameter* It 
connects are known. In that case the unknown one ii determined from the others, tf more than 
two are not known, the demon is helpless. 'Because of that, no special action is nece*t=ny if one of 
the known parameter values is o-\,lcd. &ul it can alsn happen that all v( the piunmerers air known, 
but at least ohe- of them is an alj^ebrsic ekpiessirin containing a symbolic unknown. The equation 
of the law can then be used to solve for : he value of the unknown. Tin? is fine and dandy until 
one of the circuit parameter*' values is ett/ed, because of backtracking. After that, though there is 
not enough information any more to solve for the symbolic unknown, it is still possible to compute 
the missing parameter from I he c:hcrs E-'or this, the demon must be iun again, That is brought 
about using the mechanism of forget -functions . Any assertion can have a target- function, which 
will be called whenever the assertion is forgo;:en qt merely mtfed. In this example, a specul 
assertion called the CHECrTP assertion is placed in the dependency-chain between the assertion of 
the value of the symbolic unknown and the facts used as the demon's antecedents. Its only use Is 10 
hold on to a forget-funuion that will requeue the equation-demon if the CHECKED assert ion ever 
vanishes {because one or the circuit parameter! in the equation was forgotten). In fact, the 
CHECKED assertion is necessary even if there is no symbolic unknown in the circuit parameters' 
va,lues, since it is still the case that if one parameter is forgotten it can be rededuced from the 
Otheii. Note that in thli case the equation Of thedemen has given no new information about the 
circuit, showing that the equation was algebraically dependent on the other equations de&crJbitfg' 
the circuit. Such an eVent happens at least once per circuit. Since at each node KCL. K irehof f 's 
current raw, states that the sum of the incoming currents is iero h and (hat set of equations n not 
independent; KCL on any on* node follows from KCL on all the other nodes- 
Some monitor demon* hav* iht abilny to predetermine the itate of a device, eliminating 
the need for searching. For example, if I -RGH| TOR-u I DDE sees a nonzero current in a diode, it crtit 
assert that the diode ii in the DN state. When a device-state choice is f^red. all the moniiors that 
might be able to predetermine tlie s;a te Choice should be given a chance to do so. This is also 
implemented by 3 forget'lMinctlon. 

Monitor demon* often check She sij/ns of currents, or otherwise lest inequalities. While 
equations are quite happy with algebraic expressions, inequalities are $tymn*d by them ^unses.5, one 
uses a more sophisticated algebiatc manipularion package than ours). For example, if a transistor's 
emitter current is assigned a value which invplves a symbolic unknown, IE-MUNI F0R-9JT will be 
run, hut will be unable to perform its function. Fi'esuma.hiy tha* unknown's value will eventually 
be learned, and it is essential thai 1 E-riOM T0R-3JT be run again then, or else a contradiction 

might go unntKiced and a fabe anslyili bt accepted That is brought about by means af the- 
HANGING assertion, which records the name of a demon (and K£ arguments) slid the name oF a 
symbolic unknown whose value- the demon IS waiting for. 1 E -HON [ TTJR -&j T itself makes a 
HAWG3NG assertion when ll w*i such mi obstacle. Whenever the value of a symbnlir mAnowi m 
determined, a check n mads far HANGING assertions tiding jt, and the demons (Key mention are 

The above examples are not ;he only cbses in which demons need tg be requeued; some 
are quite obscure The examples described should suffice toihow why the queue is, a constant 
source of bugs. Because of iha;, we have given thought io possible mechanisms that might have 
the same modulariiwg ability as the queue, without iu fragility. One which was actually 
implemented at one time was to keep the queue inlVnttilon in the data lias* of ram. The 
dispatcher which now removes entries from the -queue and processes Lhem. in that implementation 
used to scan the data base :"d:- possible places ta run demons and run one. The only new 
information that had TO be stored was the list of demon-invocation! already performed. -- in the 
form of Ft HAS-^UN assertion for each successful demon -in vocation -- so thai the dequetier could 
avoid running- demons redundantly, This eliminated all danger of accidentally Fosing an entry 
from the queue, since the whole queue was ef fectiv*ly recomputed each Lime it ivas used. Tt also 
made CHECKED a Hermans unnecessary, since the (fte/ing oF a HAS-RUN assertion would 
automatically subject the demon to being- rerun. Unfortunate^, in our implementation, this 
mechanism proved to bt unacceptabty stow. "" 1 '* 1 '" 

The Data Base of Facts and Demons 

ARS stares all problem specif it: knowledge in lhe Form of facts or assertion! In an 

Indexed data base. An example of ft fa<t Is (- [V-ni.TAHE IE Dll f 1,31 h which EL tales to 
rtieah that QTs emitter voltage |i 1.3 volts. IAL TFRWAT I YES (MODE DJ00E> CON DFFH says that 
the device-st^te of * dtode, known hi EL as its MODE, has two possible, values, called ON and OFF, 
The first sample fact h typical of many of the t acts EL generates as It runs. The second is 
actually pari of EL, and represents tnowledge appropriate to choo&mg diodes' states. 

Tiesides its statement {which h what " 1- [VOLTAGE [E 01 M 1 , 3T is), a fact alio has a 
unique' factnafne, which II ft US? atom. The f actname's LISP property list IS used to record the 
fact's auxiliary information, SUC-h as its dependency records, whether Lt li currently believed, its 
fOf ge-t-f UJPICtion {see below) -■ everything other than ju;^ "whal r.h? fftcr i»yi" In addition, the fact 
Is referred to whenever possible by its Tactnarw fin dependency tecords, for example), ft is 
tempting, when using a relational data base. to break ill knowledge into small pieces and make 
each piece a separate assertion. That can lead to great inefficiency, as. we discovered when using 
early versions of ARS. Since then, we have rewritten ARS 10 use the indexed daia base Fnalnly as 
a way of placing property lists on arbitrary LISP Hsu as Jf they were atoms. One might suggest 
that a simple hash table might serve, but that Is in fact how Ihe data base is implemcnLed 
anyway. E *" Wl ' 

EL record! the names of the devices in a circuit with [S-A assertions, such as 1 1 S-A ftl 
RESISTOR) or H5-A NE^ NODE! , An EL demon driven by those assertions controls an ARS 
mechanism for typed variables In the trigger sfc« of laws. Whenever an I S-A is asserted, a LISP 
property Is placed on the device's name that identifies It as a certain type of device. The pattern 
matching mechanism that (rigger* demons I hen Insists that a typed patlem Variable {such as R. in 
the demon DC-OHM) match only the name of a device oF the appropriate typf 

Demons In ARS are program* subjeci to pattern directed invocation. Each EL demon 
generally implements, a single item of knowledge about electronics {though a few embody more 
general problem-solving fcnowfedge)- Here,, for example, is the dciTwn thai embodies the fact that 
all Of the current into one of a resistor's terminals cOrfttS uUl the Other one This law i^ needed 
because the fact data base is not constructed ia as to retrieve (CURRENT U¥l HI! I and ICURRENT 
Hff2 Ffl)> from The wme pfote automatically 

tlAH DC-2T-R A5AF t [fl fl£5t5T0Pi [1 l£i 

{[- ICURREHI (tfl !7RU 1>lll (-.(CURRENT W2 I7RIJ f>l2JI 
tEOUAiluN h t*+ 11 I2r 8.6 RJ I 

Its name, chosen by us for mnemonic significance, U CX-ZT-fl. ASAP indicates its in vocation 
priority. DC-JT-R uses the local variables 11 and I? to hold the two- terminal currents. The l^nft 
list beginning with t- (CURRENT , . T contains the demon's (rigger slots Then pnrpo.se in dual: to 
provide patterns to direct the invocation or trteeerlne of (he demon, and to gather the information 
needed In applying the law once the demon is Invoked. 

When the function LAU, a. LISP macro, is ailed recreate the demon DC-2T-R, it stores 
information ^ bout the trigger sbrs In the demon dais base, which has the farm of a sty hied 
decision tree whlcl-i. applied (0 a fact. quicVly find* those demurs which have at least one trlg-gei 
slot thai matches the fact. Each of those demons has c^ of rhe facts it needs to be able to do 
useful Work; Jt might or might not have all it needs. ARS enqueues them all for invocation, and 
the demons themselves m-.j.^ deade whether "hey can da anyrhmg. For that h They USe the trigger 
slots. again, applying them all ai patterns co the fact diaia base. Thus, if {- (CURRENT tflfl Rl 1 > 
10.3) ii asserted, dC-2T-ft will be triggered, and the value maiched by the part variable H will be 
remembered as an argument ((he declaration of =1 as [R RESISTORI will prevent triggering unless 
what ft matches is actually the name of a resistor). 

When the demon is invoked it will apply all of its trigger pattern* to the data base, using 
Its argument as the value of R timing the match - that is how we mate sure that we find! voltages, 
current and resistance for a single resistor instead nf for four different resistors^ Variables 
appearing in the p&tterrt whTi the "V operator have no effect on ihe triggering of the demon, but 
at the matching stage they are assigned whatever value they happen to match, j/che pattern 
matches anything at all. Thus, if in addition to Ihe triggering assertion about the voltage at Iffl 
Rll. thetworatts {. [VOLTAGE [fl? Rl)\ 9.9} and f~ 'RESISTANCE RII 1090,6) were in the 
data base, DC-QHM's. matching phase would jet V\ to 10A ^2 to 0.0, and RE'S to 1000,0, 1 would 
remain NIL if there weie no assertion about the lvalue of iCURflEHT [fll Hllt H 

In addition to jetting local variables, the matching profess places a lis! of the faclnames 
Of the ficts matched in the variable ANTECEDENTS, along ivtth the demon's demtjnn a me . IF the 
demon asserts any new fact, it will normally supply Ihit list as the antecedents of the fact. ThLs is 
how the dependency records obtain the information of what other facts were used in deducing the 
new one. 

After the k m*rtrimg phase, the body of the demon is executed. In this case the borty is 
Just a caH to the function EQUATION, which does all the wor* of extracting any possible new 
Information from the specified equal Ion and <hr pa rameici values obtained by the match phase. It 
also knows how to report a contradiction if the parameters have values that can't fit the equation, 
and that there IS nothing to be clone if too few nf the parameters J re known vet. 

How It works: 

ARS has three different storage representations for the three main types of entities it 
knows: facts, demons, and dependencies. Dependencies ate .stored a j simple LISP lists. Each fact's 
factname has a CONSEQUENCE'S property which is a list of ihe •actnames of all the facts deduced 
from it, and an ANTECEDENT -LISTS property which is a list or lists, one list for each way the fact 
has been deduced, containing the facmames of the facts used in the deduction. 

A demon is more complicated. In addition to the LISP function Which implements its 
body it must enter tts trigger slots in a data base that allows that slots that match a given fact to be 
found easily. Alts compiles the trigger slots Into a decision-trec 0iIfri " 1 * ,fli, ' , wl1 which it builds 
Incrementally. The tree specifies locations in the -art being matched against (such as, "'the CAR of 
the CAR of the GDR"), and thro various things to compare it against, each leading to some 
demons or to further decision*. 

The fact data base is the most complex of the three It is a bare-bones version of toe 

Conniver data base. It indexes each Tact by each of the atoms in it, (ctgcthef with Jts position, 
Thus, the fact I- (VOLTAGE EG Qll) 1B>0> would be Indexed under "- In the CAR", 
"VOLTAGE in theCAADR*. "B in theCAAfJADK'. "Oj in the CADADADR". and "10.0 io the 
CADDR". Thfc method ctT Indexing nukes it easy to look for ail the fact! that match a pattern 
which has same positions unsfeclf led. In ARS's notation, ' >FDO is a pattern which matches, 
anything and sell FOO to what was matched. I- (VOLTAGE IB !>Q!T !*V3 ought 10 match any 
assertion about the voltage on the base Of something. AR5 can find all the facts that It matches by 
looking In the fact data hate inde* under "■ in lheCAR H > "VOLTAGE in the CAADR". and "E 
In the C A At) ADR", and intersecting those lists of facts. 

Actually, the indctt-pans of atom and location! art hashed into a fixed length table, so a 
bucket may rgntain thing! that are irrelevant to the index-pair being Fetched. For that reason, an 
actual matching test must be made on each fact thai the indem returns. 

Originally, aH three types of data were kept in the fart data base. Facts were kept as lists 
(<5,ta.temenL> FACT tfactname*),. demons as lists (*slot> DEW ON <demonname*), and 
dependencies as lists (*factl> DEFENDS <fatt2>). This had the advantage of being easy to dc r 
but was Very inef f klent- This was obviously SO for dependencies, whose representation we 
Changed shortly after AR5 began to 1uO> at them dining normal operation. It was not nearly so 
obvtoui that this was a bad way to store the trigger slots of demons. That was discovered only by 
timing measurements. The problem was due to the fact that the search operation for derrron ibis 
11 different from the search operation for facts. Facts are searched for with a palrem like I- 
I VOL T ACE (B !>flr) l>V> , and wherever it has an atom, all the facts it matches must have the 
same atom. On the Other hand, when a fact such as U (VOLTAGE- IB Qi>> J 9-8) is asserLed, ihe 
slots that should trigger mi^ht differ from ih* fact ttself in any position. For example, (■■ f '^QTV 
<>TERM]NALi L0, 0) should be triggered If it exist*, as should U !>ANV THING 1>VALUEI. 
£! DELATION (VOLTAGE fB "^03 1 !>NLrT1BER), [- ll*QTY l!£GB !*Q}> LVALUE}, or even 
just !>FACT if any demon has it as a slat' The Tact data base is poorly suited lo that retrieval 
operation. The Implementation of a separate demon data base resulted in a factor of two 
improvement in the speed of ihe entire system- 

A lewon to he drawn from the experience with the ARS data base U that it is usually 
worthwhile to factor the retrieval problem We had a data base whose entries could be divided. 
etiily into three classes, such that any crtrieval would certainly be looting for entries in Oflljr one of 
the three. Now we have three data base systems one for each-class. 

Wf chink this corrected mistake Is worth men tinning because it Isn't a new doc - 
Conniver made the same mistale^ IF- ADDED methods were stored in the fact data base and looted 
. up Just as A RS demons formerly were People have often assumed that the slowness of Conniver 
was due to- the basic interpreter, but in fact measurements '.showed that Conniver spent rm>st of its 
lime searching the data base. Our results with ARS F.urvgest that Conniver also might run 
considerably faster with ARS's newer demon data base. 


Our research strategy has been the application of artificial intelligence techniques to the 
construction of an en pert problem soker in a non-ti ivial domain. We feel that ihjt strategy has 
been very fruitful We have developed two methods. Otic is a rushed of elecintal network 
analysis we call analysis hy props Eation of opnsframrs , The Other is ihe technique of efficient 
combinatorial search by dependency-directed backtracking . Analysis by propagation of oonslra mts 
would riot have been developed m the absence of such artificial rrptelligentc Lcchniqurs as synhn lir 
manipulation of al fttbraic ex press ion J and a ntecedent reason jtig . Dependency-directed 
backtrack in| is a new artificial intriUginc« lechniajue ^hose development was stimulated by the 
needs of this exceptionally deep,, yet well-slructuied domain 

Electrical circuits is. an especially gcod domain in which to develop artificial intelligence 
techniques Reasoning about circuits Is deep enough to benefit by the applicaltnn of powerful 
techniquei, yei the problems, are drastically simplified hy the fact that, the interactions between 
parts of a circuit are well-defined and constrained to occur by explicit connections. Another 
advantage is that it is clear whether Or rtnt an answer tendered IS in fact Correct. 

An even more important reason for si tidying reasoning about electrical circuits is that 
such reasoning ls typical of the icasoning done by all engineers, including computer pi Ogisinniei S 
We wish to understand the nature of reasoning- ibout deliberately constructed sysrems. An 
understanding of the epistemdogy of engineering will enable us to make program* which can 
.significantly aid the design and debugging of engineered systems, including compter programs. 
We expect that such an understanding will entail (he development of techniques concerned with 
many aspects of reasoning, ^eluding constraints, causalny. and teleology. 

Generality and Extensibility 

ARS is a language in which it is easy to embed problem Solving rules for domains in 
which the solution to a problem may be obtained by the symbolic relation of local constraints It 
provides special features for explanation of its conclusions to its users and it uses this ability to 
provide for reasoning hypothrcicairy and for efficient combinatorial searches. We are convinced 
that the ARS paradigm is applicable to a wide variety of domains. Jon Doyle cDoyle J9?f>* has 
looked into the possibility of a set of AR& rules to pro^c theorems of ptanp geometry {no 
constructions) along the lines previously investigated by Nevms tNevins IS)7*p Matt Mason 
<Mason 1976* has constructed a, set of rules for :he analysis of the flow of materials and money in 
a hog farm. 

EL, the set of rules of electrical circuit analysis, is a very pleasant system to work with. 
The explanations ir provides (o a user can be useful for helping understand the behavior of a 
Circuit — how particular device parameters affect thrr hehavior of Interesting circuit parameters, if 
a particulai answer is surprising it is p&SSibk to find cut why EL thinks that that answer is tro#, 
The User can have more confidence in these answers because he can chert the reasoning. The 
complex programs of rhe futuie will most certainly have ro use Similar techniques so as to be 
responsible- for 'he;: ,i in v-t , i j 

EL is very extensible because of the modularity imposed on it by the conventions of 
ARS. It is easy to add new device types to EL because the rules for the ne^ elements can be 

constructed In isolation and usually do not Interact with the laws for the culsting devices This, ii 
even true in the case of macro-device* because the macrn'device gets control of the selection of 
States, for It* parti. GeniM, Roylance <Roylance Wh> crealed rules for (rtCHJgh macro-device types 

to allow the analysh oF the 7H1 operar loni I amplifier. In fact, Lt would be easy to add enough rules 
to create whole new analysis modes. To add sinusoidal steady state analysis, for example, would 
requite only a set of laws which chancterlied parts in remis nf impedances, and a small e*tf nsinn 
to the. algebraic manipulation package to allow the manipulation of complex qUflnllNeJ 

Problems and Plans for the Future: 

There are many modes of reasoning about circuits which we have not captured in F.I. 
Some of theae, such as sinusoidal steady stale analysis arc really my Simple extensions which we 
have just nn: yet fyntlen around tn doing. Others, however Stc much harder and may represent 
more fundamental problems with the ARS paradigm For embedding of knowledge, 

For ex ample, it Is not obvious bow to represent the Vnowledge required to do tlme- 
dorrvaln analyst In ARS In steady stale, dc, or incremental analysis, it is possible to summarize the 
entire behavior Of a network unknown ax a simple, algebraically rnantpUlable expression Time 
domain analysis requires explicit u'me functions, some of which might be algebraically h-O-irendnus, 
tq be manipulated. Gerald Roylancc ^Roylance r#76> is besjirrh ir>g to investigate what XI rids of 
qualitative reasoning is required to bypftis this algebraic roadblock. 

Simple equation demons are an essentially declarator representation for equality 
constraints, even though demons are procedures. Inequalities me |-pp resented as monitors and 
cannot be manipulated easily. This leads to the following problem 

VW — i 

In this circuit, the on If pbyikally consistent states for the diodes to be in is both conducting. If r 
however, we; assume both are- cutoff, EL wilt not discover the con-trad iction became that would 
entail the propagation of inequalities. De Kker <At K1«r I9'?&> solves this problem by 
propagating ranges, but he cannot handle symbolic expressions at all. We are looking for a way of 
handling Inequality wnsttaintS In a more declarative manner thRn by monitor demons 

Another problem is thai although EL can use grey-box laws which embody certain global 
abstractions. EL does not make use of the genera i ^i I valent circuit ideas in its analysis Thus, lor 
example, one can declare a particular circuil to be an ampliFier by its identifying nts input and 
output terminals with those of a Special macro-device which speciFies that the inc rem'.-rt? ? I tfnlrsge 
on the OUt-put is propn-rTional to the Incremental voltage on the Input (perhaps with an unspecified 
gain). £L can then deduce the value of the gain by Working out the Incremental output voEtage 

for a given incremental input voltagf. The problem Is that this value of the gain- depends- on the 
particukar Incremental input voltage used, 10 derive it. Thus, it cannot be ujpd to compute the 
incremental output for any other value oF input ilnte for that value of input the gain would be 
flit. This Is basically a. problem of the tntera'.tipn oF context! with logic. We rreed a mechanism 
by which the value of the gain can be made to depend on the teaso nl nfl behind the value of the 
incremental output voltage for the given input voltage rather than their values. 

A related probtem is what we -call "anomalous dependencies Consider the following 

In thli -Circuit the current through the resistor Ji independent nf the value of The voltage At the 
bottom node of the circuit. The justification of the value of Che current produced by the EL laws 
will, however, include thus voltage because If was. propagated through the voltage jounce to produce 
a voltage at the top. Ohm's law was then applied to Lhe difference of The voltage at the lop anct 
bottom nodei These cSlra dependencies can increase the amount of search the program mint go 
through because they can Introduce extra assumptions in 1he proof of a contradiction. We have 
not„Jhowever t hAd this cause much trouble in any circuit *e have analvied. 

More generally, the AP.S paradigm dpes not elucidate the mechanisms which guide and 
focus a problem solver, AR!> rule sets are capable qF capturing only antecedent reasoning. Thus 
ill deductions which can be made are made. This is only accepTable m domains which are self- 
limiting - In which there' are only a finite number of questions which might he asked And any of 
them mtght be releyenL, Indeed, there is no means in ARS of focussing effort on the aspect of a 
problem which IS being- asked about. Consequenl reasoning is one approach to model this part of 
problem solving ability. More generally, rules To control the i luw of reasoning may need, the 
antecedents of a fact to he more temple* -- one may want a fact to depend on the fact that another 
fart Is false or even worse, unknown. Jon Doyfr is no* investigating a genera H ration of the ARS 
dependency .scheme in which this ■; possible 

Appendix: An AniinUled Esampk 

This append!* documents a complete run of EL on the Foliating' circuit. It demomti Ales 
how EL nay be Used not only to analyse a known circuit, but to help specif y the component vain*?, 
to product desired behavior. 


I GRvWft 

Our type-in Ji In lower; case JO distinguish it from ARS's output. The scenario is complete and un- 
cut, Do not hesitate to skim through king runs of ARS output not punctuated by English 
(Ornnientary; Ihey ton Lain more esampks of types pf reasoning that wpre already exphmfd ^lier 
they first appeared. 

Flint we Input ihe Circuit diagram, specifying the namePRGT^ for the circuit. We decktri? 
the names of The transt&tOll, and tp-eeify then' polarities and which semiconductor mateiial ihey arr 
made of. Ogi indicates a Slllton NPN Lranslsior. Similarly, we give the names of all the iEsislors r 
and their resiJTAnces in Ohms, Note Lhat the name of a resistor dcpjn'l havr to begin with "B"; it is 
just the standard electrical engineeri convention to <\o so. Cajiactto-n are specified with their 
value* in. fjirsdj. Currently (he Values arc ignored, since analysis is done only For zero and infinite 
frequency. We then describe fhe interconnections of the devices E-auh aTgUmcnl !o CONNECT" 
describes one node in the circuit by stating which terminals ate incident wuh it. Each type of 
device ha* standard names for its terminals: for resistor* and capacitors **l" and *JS2* for 
transistors, "E", 'B* and "C" A terminal lia list whose second element is a device, and whose first 

says, which terminal of that device, as in <B HI I Foe Ql\ hi.it. Certain nod?? become ^terminals" 
of the whole circuit, considered as a mjcro-df'vire, ?hey are f iven explicit names. Mich as GROUND, 
which identifies the node which will bewme the terminal (GROUND PRQT2I , PRQT2 has four inch 
terminals: GROUND t +VCC, INPUT and QUTF1.JT, 

--* {uir* prot2 

(bjt Cql 9,6) <Q? 0.6J <cr3 fl,Gi (q* 0,6) IqS 0.GI1 

{r»igtor Irl 370000) IrZ iwa£3> [r3 1090&1 ( r 4 1409) k& SG00> 

Cr6 G3&1 Ir7 33001 (r8 2200) <r3 10001 [riff &800I Irll 470) 

friz 350001 fri3 5200a n 

[capacitor feci 2,0e-7> Ccc2 U0i-£J Seel l-9e-4)> 
(connect Ltvcc (Sfl rl ? (ffl r3) Iffl rS) <tfl rlZf Ec q4) I 

(ground \#2 r2) (#2 r-4) (#2 r?) (#2 cbl) <«r2 rl3l (#2 r&i) 

[inpul Ul ccLJl 

[W2 cell [« rl) 101 r2J (b ql)l 

[M2 r3l <c ql) (c q2i (u q3)i 

Ifo ql) (h c£)l 

(fa q2) {£1 r4)i 

(IA2 r5) Ic qll 1*1 cc2Jl 

U#2 cc2f [R ri2) (JTl rl3> fa q*S Ic (£)) 

I fa q3) [ffl rGl) 

l(#l r7) iff2 rG) 1*1 cbll) 

<(b q&j (#1 r9> Ml rial! 

- ifa qk} m rii) lire rien 

(output (b qS) (#2 r9) Itf2 rill Lfli r&l ) 1 1 

Now we supply boundary conditions I"ot rii» circuit ARS supplies a unique factname Tor 
each assertion we mate, as it indexes the fact in the pattern-directed data base. The fa.ctr.iamc of 
an assertion: is used for remembering its atlribuics or prnpcilics, such as how it was deduced., and 
what other assertions were deduced from it. All hough an assertion could have an arbitrary form, 
the assertions meaningful to the RL system full mini a few schemata. 

U IVGLtAGE (DHQUND PRS1T2I ) 3.0) is an esample of the most common schema of assertions, in 
EL; it states that a particular parameter f VOLTAGE) at a particular terminal (namdy, 
IGRGUND PRQT2)) is known to have a Mr tain value (0,0). 

VOLTAGE" and CURflENl refer to the DC analjrit of the circuit, while tHC-VOLTS and |ic- 
Wt*S refer to the infinite- frequency anatysu. 

The first fact created is fact F22G,. because numbers I through 2£5 were used Up by EL'j 
initial knowledge (facts and demons), and by the assertions made during the wiring of the circuit. 

--> (tell '[voltage (ground t?r<ot?l) 01 

— > {tall '(witapi t*v« p^el2} J LSI 



-■* (tell * icurrent {output prat2ll fl.flf 

USER: F22a (- [CURRENT (OUTPUT PflDT21l 9,9] 


--:■ (tell '(tnc-wolts [ground prot2)> 0) 

USEE; F223 {» (INC-YOUS [GROUND PflrjTJr) 9.81 


— > (tell ' [i nc- vol ti (#vcc protZJI 9) 



— > itcll ' Clne-anpB Output prot2)l 0) 

USER J F231 (- UNC-ArPS 1 0UTPUT FflDT2'H 9,9] 


--> (tell ' <inc-voIt& {input prot2) I 9.1) 



Not all Che voltages and diluents at thr circuit"* term&nak have been specified, just . 
enough to solve the circuit. Theonei we did not give will be computed by EL as the circuit it 
Aolved. II might l>.e Surprising (hat only thren DC boundary conditions are enough for ft ClfCUlf 
which has four terminals,, but they are beanie the capacity CCl supplies what is effectively a 
fourih boundary condition: (- ICLRREMT liNFUT PR0T2) I 9.9). . 

The wiring of thecitcuit, and the s-eccmg: nf boundary conditions, have suggested TO EL 
deductions to try to make. At this point we tell EL tp follow ehEm dui as far as they go. Successful 
deductions give TX yet Other suggestions. (HUN) will fcrminaieonly when EL has no idea how 1d 
deduce anything more. 

Each deduction is made by a "law" which Understands on* particular ftvaf theorem qr 
mle-rjf thumb about a particular device type. Examples ate Ohm's taw for remtots, and th'i law 
that the base current of a transistor must be very small. Each deduction records the fact deduced, 
its, fac.iname„ and the name of the law chat deduced it For example, DC -ZT -5HQRt is Ihc law that 
the current into one end of a wire or 'short" must equal the cut rent out of the Other End. 

■ ■> (run) 

DC-CPftQPt F233 r- (CURRENT (41 U2I4I1 8.01 
DC-2T -SHORT i F23* [- (CURRENT 1ff2 U2141 I 9,9) 
DC-VPROP: F235 (- (VOLTAGE [« U133I1 15,9) 
DC-SHORT s F23G (- (VOLTAGE M2 1413311 15-9). 
Oe-ffl-: F237 I- {VOLTAGE 1C QUi 1S.B> 
DC-KYL: F23fi 1= {VOLTAGE Iflt R12JJ IS. 81 
DC-tfV|_: F233 U {VOLTAGE {#1 RSI) 15,9) 
DC-KVLt F248 I- 1 VOLTAGE \»i R3H 15-9) 

DC-KVL: F241 (- (VOLTAGE (Pi RlM 15.B) 
DC-VPROP: F242 I- (VDLTAGE (#1 UUSh) 0,01 
DC-SHORT: F243 I- (TOLTAJGE <02 U14EI ) a. 01 
DC-KVLi F244 {. (VOLTAGE W2 &&>) 0.0) 
DC-KVLi F245 {<- (VOLTAGE (02 111 3) f 0.0) 
OC-ICVL: F?G& I- (VOLTAGE (02 CB1H 0,0) 
DC-CVL: F247 (- (VOLTAGE (#2 F7Hi 0.0} 
DC-KVL: F2^S l- (VOLTAGE <02 fl4>] a. St 
DC-KVLi F249 f- (VOLTAGE UfZ H2!> 3 r «h 
PC-CAP-li: F2S& C- I CURRENT (#1 CB1H 0,01 
CC-CAP-12: F2S1 I- (CURRENT (« CBlM Mf 
DC-CAP-] 1: F2S2 U (CURRENT (01 CC2M S.M 
DC-CAP-12: F£$3 U (CIRRENf <02 CC2M 0.fl> 
OC-CAP-11: F254 U iCUflRENT (ffl CClH 0.01 
DC-CAP-[2i F25& f- (CUFRENT 102 CC1)1 0-0) 

The following NEEDCHG1CE assertions drive (tie mechanism (hat chooses states Tor the 
transistors in the circuit, by (lingering the demon that doe? the choosing It is. just a coincidence 
that these assertions, happen now, when sU the sign if leant deductions have heen exhausted, thcy 
mighr just a* well have been the firsc assertions made* since *he demons <ha< tb-e-jr ti'Eg; Br ha^e a 
special low priority that guarantee; that the/ win nor, run until all deductions have been tried. 

THY^BJT: F257 (NEEQCyOiCE (rtfflE 05 )> 

TRY-BJT: F25& (NEEQCH01CE mDDE 0*1 t 




There are now no more one-step deductions, available without Assuming slates for some 
of the transistors in the circuit. For the nonce, 3 tiansistor In EL ha* l hew State.* Oi ^mewips": 
"beta-infinite", "cutoff", arid "saturated". The system Will try chatting one mode and later try 
others instead if the first guess leads co a contradiction. After guessing the mode of one- transistor, 
EL sees what can be deduced about the circuit before gueUlfisj, (he- rieiit. Thai Is in the- hojM> that 
some of the deductions will limit the possible chokeift* other nan sisters nor yet gueucd. 

DC-BJr-BETA-ENFlNtTE: F2G4 U (CURRENT (B 01)1 G,0300001£-1G1 
DC-BJT-BETA-ltflNlTE: F2&7 [- 1DURFIEHT EB 021 1 &.00000&1E-1E-! 
DC-KCL: F2G8 (- (CURRENT IE Oil) -€. 0003001 E-1SJ 

Think of LNDEflFLDU as a very small number. It js our way oF frying: t° avnid fhe 
problems caused rjjr rht nonaJSMjaiLVity of floating poin! addition Et is The result obtained wIipii 
two large, nearly equal numbers have been jubtracted and all prpciiicn lost IS'o contradiction 
results from equating UNDERFLOU to «ro or to att/ small enough number. 6 COOOOQIEIS, on 'he. 
other haml ii a number which, while small corni|>ar-edt co all ch«: qifantici« of interest in the system. 
is nevertheless definitely iff-,' equal [0 IfrO. We MSt it CO reprcseni the small but certainly nonzero 
current into the base Of an active tiailSJStCW. SO chat a Con-tradicCion will occur it 7 anything requires 
that it be exactly zero. 

QC-BJT- BETA -INFINITE: F272 t- iCJdFWENT [0 Q31 1 6« WBB0&1E-1S1 
DC-BJT-BEIA-ltf [NITE: F275 f- (CURRENT (B 0*) f G.&3ea0BlE-l&l 
OC-BJT-BEIA-INFINITE: F27S i- (CURRENT EB rj5)l 6- 03^00 it -16 3 

Th« current state of knowledge is:. 




The system has again run out of one-step deductions. Since states have been anuniert 
for all of the components that need them, : he aril y pf^ibc Lauie is that the Circuit contains *n 
essential simultaneity of equations, and a symbolic unknown it necewary w pj-oceed Farther. The 
sysSrm create* a "symbolic unknown" X.279. and anigns il as the value of CHIC of the unknown 
voltages. This unknown can be propagated around via one-Ken deduction jwsr as a numerical 
value can be. Eventually, when the "cycle" of simultaneous equations is "closed" by examining the 
last equation In It, all of its terms will reduce to expulsions involving >:27S< whose value will then 
be determined (see assertion F3Z3). From then on, whenever nneof the previously propagated 
captions involving X273 (I referenced, X273 will be replaced with its value and the new 
expression will be simplified. Sometimes it happens that there are two coupled" essential 
slmultaneiciei; in that case The system win run out of (Kings to do a second time berorc figuring 
out the value or ihe unknown. Et then creates a second unknown and fhe two together would crack 
the simultaneity. 

C£MVARS: F2B1 I- lYDUAGE t*l RBI] K2791 
OC-KVL; F2SZ 1- (VOLTAGE 1(12 HID) K2?3> 
DC-KVLt F263 (- IVOLTWE iff 2 RS>> H£"9> 
DC-KVL: F2S4 I- (VOLTAGE (E Q5M X2792 






















DC-JCVL; FZ85 I* <V(XIACE (A2 14214)1 X279J 
DC-SHORT: F2SG (■ (VOLTAGt (41 UZ14J1 X2791 

Note that algebraic expressions, involving the symbolic unknowns- can be handled when neWMary. 

DC- BJT -ACTIVE* F2fiB f- {VOLTAGE (B Q51) C4+ ff.G K2731 1 
YBE-M0N1 TDR-flJT: F2S9 (HAUGING 07 1 OS K279f 

(VOLTAGE [fll Ran («+ &.$ X279H 

(VOLTAGE [01 R18IJ 14+ 0>6 KZ79J) 

(CURRENT [tfl R9)| 6,3ew9eiE-*j 

[CURflENI (#1 RlflM -E, BaBBd91£-4J 
[VOLTAGE in RlfllJ 14+ 4.EB3BBB1 K279JI 
(VOLTAGE (ffl RUH <4+ 4.GBfl&flftl X279)) 
(VOLTAGE (E 041} i&* 4.Gaaca»l H279> > 
DC-BJT-ACTlV£i F237 (- (VOLTAGE (6 Q4H (4+ &, 2800081 K279J J 

When states of components are assimypd, it is necessary to check [hat the consequent 
circuit parameters agree with the l(nawn general conditions for the component (c be in Ihose 
slates. Such checking is done as soon as the necessary information is available, by demons known 
as monirors , One such monitor is VCB-H0W]TDR-BJT r which checks the voltage drop between the 
base and collector Of a transistor for consistency. In this case. s,ince the Value just learned for th* 
bat* voltage of Q^ involves, an unknown, the monitor can't tttl whether it is legitimate. Er will be 
necessary to checx again when the unknown \ value becomes, known. To that end, the monitor 
makes, a HANGING assertion which associates that unlnown with the need to apply thus monitor, f oi 
(his particular srarisislor. When the value is eventually learned, the HANDING ajscmwl is n«ic«l h 
and the monitor I* tested once agsun with the new mfomialiori 

VC&-rJ0NtlQFUBJ7] F2S8 1 HANG INC D70 04 X279I 
VBE-".:V["GR-BjTt F233 1 HANGING Q71 04 X2791 
DC-KVL: F3S8 I- (VOLTAGE (C 051 1 Ii+ 5. 2Beflff9l X273I1 
DC-KVU F3S1 £- (V0LT*GC (Al H131 1 (4+5.2*89831 H279) I 
DC-KVLt F3S2 (- (VOLTAGE (02*12)1 (*+S,2£&3801 K27SI > 
DC-KVL: F.383 {- (VOLTAGE (#2 CC21 1 (4+ 5< 2880801 H2731) 
VCB-nQNIIQfl-BJTi r"3B4 (HANGING D70 05 K273] 
DC-OWt F365 (. (CURRENT (ffl R12» 

14* 2,432307GGE-4 (4* -2.S6<U025GE-& X 2731 1 1 
OC-ZT-Fft F30G [- (CURRENT (32 R12M 

(4* -2.4S23076GE-4 (4* 2.&E4102&GE-5 X279DI 
DC-OHIt F307 (» (CURRENT (#1 H13) > 

(4+ S.439K24EE-& (4* 1.21 351 22E-5 XZ79)1) 
DC-KCL: P3fiS C- (CURRENT (GQ531 (4+ l,348*B5ZE-4 <S* -3.7&3G147E-5 X279r>> 

NOTE -SATURATED* F31fl iHAUGIHG D72 05 K273|i 
nC-ECL-BJT: F31L (. (CURRENT (E Q&] I 

(&* -l,8484052E-4 1&* 3.7&3&l*7E-5 XZ731 J I 
]E™nON|TOF-BJT( F312 (HANGING DB5 05 K273J 

DC-2T-R( F313 (- (CURRENT ISZ fll3) I 1*4 -e.«36245E-5 18* -L.2195122E-5 X273>>> 
OC-OHH: F314 U {CyfiflENT Ml RUM 3.S57447E-3J 
DC-2T-R; F315 I- (CURRENT Uf2 (till I -9,357*47E-3f 
0C-2T-R: F3iG I- fCUflREHT («2 R18)l G. 0O0Ba01E-4J 
DC-KCL: F317 U (CURRENT (E IK I) -8,010557*471 
DC-KCL-BJT: F318 f- (CURflEttT iC Q4l t 0.010557447! 
DC-2T-H; F319 {- [CURRENT IS2 R91 1 -$.8060(30 IE -4) 

DC-KCLi F328 (- (CURRENT ItfL A£l) (&+ 8,8187422875 («* -3>, 7B36147E-S H279N I 
DC -Cms F322 (CHEDKF.D CHECk321 Dl fl&l 
□C-Oltli F323 (VALUE X273 21»JSI€39ei 

Here we see that she value of the iymboJie unknown M279 U*i finally been dc ici mined, 
This blessed event was the result of applying Ohm's law ro four quantises each of whkh was 
already known in terms of KZ7S. From now on. *hc never a I** r^kes «?e of a quantity 
previously dependent hi H273, the known Vatue of K279 will be substituted for it. When that 
happens, the final result ii given an exptlat dependency link toF323. since il would be invalid iF 
X^S's value ceased to be known. Sudh fKjjliCH dependent: links were not necessary when X779 
was propagated in symbolic form, sin« those props j^ahons are valid regardless of the symbols 
vaLue, In addition, all of the monitor laws ?h4t were hanging on the value of H273 me now re run 


0* 6 GR&O^'D 

Untaa unately, our ffiftnd VC6-IKW] TDfl-BJT dtlv.te an inconsistency qVi collector 
voltage J s lower than in base voliage, even thotigh Q4 is supposedly in the active stare. When the 
contradiction is detected t the. proof tree leading io ii is searched for The component slate choices 
which engendered it. Those choices, precisely, hjvf been shown by the contradiction to be 
mutually inconsistent; A WGMD assertion Li constructed to hoM that insight and make sure that 
[he same combination is never iried again. The fewer The number if choices in the- WGOOD, ih* 
more- information has been gained from the contradiction. \n ihlS case there are only Two choices 
in The NQCDDD. Of all the 3* (24$) different jets of choices for ill 5 transistors, there are ?7 winch 
mdlJde those two (incompatible ones, all 2? h»v* been ruled out at one blow This phenomenon 
cause-! a great reduction in search Space sine, which makes EL converge in human tlmespans. 

Once [tie jyjcetn lias detei mined ihr choices thai are contradictory, it picks one of ihem lo 
re-Chow* differently {the "culprit* actually chosen blindlyj. In this case, the culprit isF27S (Q5 
active3 h the system "stops, belu-yjng' it" for the moment (bm continues to remember what it would 
imply) and tries treating- Qb as cut off instead. 

tfCB-HDNlTOff-BJT: F32S [CQflfRADICTJON C3?4 U7« Q4] 
CONTRADICT [ON I *M - F32S vr;&-rlON[TQF!-&JT 


CULPfatTt F27E urMiar k i ng ; ior- ge 1 1 1 n&s 
223 facts to check out 
163 active facts left 
1 contradictions bo far 

vc3-"i3N;Tc=i ojti F32S moooro > :-~ic~ ~i- ■ r-rTA [nhmtej 

DC-BJT-PJTOFF-IB, F323 I- (CLflRENT l& QS)l 4.0 1 
OC-BJT-CUTOFF-ICt F330 (- [CURRENT [C Q5)l B.4! 
DC-KCL-BJTi F331 (. (CURRENT (E Q&I I 9,9) 

Despite the new if ate of one transistor, a symbolic unknown is still necessary, EL piefen 
to use one already used when it is passible. As before, an assertion is made Lhal a quantity h&S 
that symbolic unknown as its value. But that assertion is identical to a. previous. no-luflgef- 
bclieVcd. assertion, F2S1, Therefore, instead of matin J a new assertion, (he system one* again 
begin & to believe F2S1. This facilitates tinmrin^ a mechanism wheieby all the old, never Forgniicn 
but no longer beloved, consequences of FJS) aire also res-lored to positions oF tins I. Uncwfinj. 1 , call 
be viewed as & sort of cache for deductions: if it were not present, the same laws as applied the 
jjievious time would succeed thjj time in deducing the a me conclusions, but with much more 
effort- Alternatively, it can be viewed as a context-switching mechanism which deals in trees of 
"logically local" j u hcofiteactL 

DC-BJT-BETA-! : LN]Tt: F2£; <- (VOLTAGE Itfl H&l ) XZT9I 

UnoutJ F2&S 1- (VOLTAGE ittZ UZ.L4I) X273) 

Uiiout! F28G :- IVD.-/.3E I*! -?:«. i v :: 7 ^' 

Uiuift: F287 1. (VOLTAGE [OUTPUT PR0T2) I XZ79I 

Unouti F284 f- [VOLTAGE [E 051 J K273) 

LWut; F283 {. [VOLTAGE (#2 R9IJ H2731 

Unoutt F282 t- [VOLTAGE (« RllD X279I 
DC-CW3; F332 (» 1CLHRE.4T r*: R6)l r** fc.WSWGE-* XZ79H 
DC-2T-Rt F333 (- (CURRENT OR HSM (i* -*.5«5«*6E-4 K279M 
DC-fVL: F337 (- [VOLTAGE (G QSM K33^1 
DC-KVL: P33B 4- [VOLTAGE (#1 RiB)) X334} 
V8E-M0N1TDR-BJT: F28£ (HANGING 071 05. JC79) 
V6E^rtQN]T0R-BJTi F339 (HANGING 071 OE X334S 

DC-OHnj F34B (- (CURRENT Itfl G9IO IS+ (A* -1.0E-3 X279) (** l.BE-3 K33411) 
CC-KCLi F341 [■ [CURRENT (#1 R10] I [6+ Lfi* l.BE-3 M2791 IS* -1.6E-3 K334M P 
OC-OHrtj F342 {■ (VOLTAGE \*Z G10] I [*+ [** -G.8 X2791 LA* 7. a X334I r> 
fJC-KVLt F343 [■ (VOLTAGE 1« fllil) (4+ (4* -6.6 K2791 (6* 7.S H334) H 

DC-KVL: F344 (- 1VDLTACE IE 0411 «+ (4* -6>8 X273) (&* 7,8 X334)l) 

QC-BJT-AETIVE: F34& U (VOLTAGE IB 041) (4+ 0.E 14* -S.& X273I 14* 7,8 X33&m 


VCS-nONIIOR-BJT: F23& (HANGING 079 04 K273S 

VBE-nCNlTOR-ajT: F347 (HANGING D71 04 K334I 

VBE-MONJTOR-BJT: F233 (HANGING 071 04 N279li 

DC-KVLl F34S {- (VOLTAGE (C 05 )> (4* 9,6 (4* -G.& K273) (A* 7, a K334I II 

OC^KVLl F349 (- (VOLTAGE IB] R|3U (&+■ r G IS* -6,& K279) «* 7.& X334H1 

OC-KVL: F359 I- (VOLTAGE [*2 R12IJ (&+ 3,6 (to •€.& K279) («* 7. A X33^JH 

DC-KVL: Fj51 1- f VOLTAGE [*2 CC2M (£+ 9,6 CS* -G.8 >:273) 14* 7. a X334H1 


VC8-M0N]TCft-BJTt F352 (HAUGJNG 070 05 K334I 

OC-0Ht1: F3S3 I- (CURRENT Ml R12J) 

(4+ 3.C323377E-4 >fl* 1.743SS374E-4 X279) (4* -2, BE- 4 X334I 1 1 
DC-2T-R: F354 U (CURRENT IM2 R12)) 

(4* -3,6323B77E-4 («* -1 . 743&£97$E-4 X2731 («* 2.0E-4 X334I M 
□C-KCLt F35S U (CURRENT 1#j R13)l 

14+ 3.C323077E-4 [** I,743&S37iE-4 X273) 14* -Z.flE-4 X334I1 1 

DC-DHM; F35S CALUE K334 14* 1.22G319IS i&* 0.S71734S8 XZ731JI 
DC-2T-R? F353 (- (CURffENT (A2 R13M -t.239G694E-4t 

DC-OHM: F3B0 I- (CURRENT (#1 HID) (4+ &. 0203516795 (&• -2.1276535GE-3 X279JH 1 
DC-2r-Ri F3G1 {- (CURHENT [« Ril)| (4+ -0.0203SiG79S (4* 2. 127E5gS6E-3 H2791M 
DC-KCL; F3G2 (- (CURRENT |#2 R3H l«+ 0,02835.1&79S 14* -2.Sez205E-3 X2791M 
DC-2T-R] F3G* (CHECKED CHECK3E-3 02 H3> 
OC-27-Ri F3E5 (VALUE H273 7.961156?] 
0C-2T-R: F3E£ 1- {CURRENT \#2 RIB} J 2.06&S3144E-41 
DC-KCL: F3G7 (- (CURRENT (E 04 M -3.&ia7074E-3i 
DC-KCL-BJT: F363 (- ICURRENT (C 04 11 3.G147074E-3) 
GENVARS: F37L (- (VOL t ACE 1ffl CB1) \ K3G3) 
DC-KVL s F372 1- (VOLTAGE (#? R6)> W35B> 
DC-KVL: F373 (- IVQLTACE (#1 R7J h K363I 
EK-OHM: F374 (. ICUBREWT 1^1 R7)} 14* 3.fl3E3fl3E-4 X3€3f] 
DC-KOLi F37S (- (CUfiHEWT (»2 RGt> (i* -3.B3&3&3E-4 X3S9] I 
DC-2T-S: F.376 I- (CURRENT (tfl P&W (4* 3.B3B3B3E-4 H3G9) f 
DC-Ka: F377 [- (CURRENT IE 03) h [4* -3.03O303E-4 K3G91 3 

DC-KCL-BJTs F379 (. (CURRENT fC 03) f C4* -6,050060 IE -IS 14* 3»B3ttlG3E-4 X3G9I11 

OC-KCLt F382 t- (CURRENT tit? H&1 > (*+ G,&0(!B831E-1E («w -3.030303E-4 H2G3})) 
0C-2T-Rj F3S3 (■ {CURRENT {«| R5(J (St 4. 0090601 E- IS (4* 3.B-3e3B3E-& X363) ) ) 





















in R5]> (4+ 15. a (4* -1.GSG9E97 K369MP 
(#1 CC2M 14+ 15.0 14* -1.G3G3637 X369H) 
(C 03 M 14+ 15,0 («* -KG9G9G97 X3G9m 

(#1 Ren (4* mseisqsj X3&9i> 

[E 03 M IS* 1.1303S31 X3G3X 
DC-BJT-AC7[VE; F343 (. (VOLTAGE (8 Q3U 14-* 0,G (4* 1.1509091 K3E9>1) 
VCB-MQNITDR-flJT: F390 (HANGING 070 03 X3G91 
vBE-MDNlTOR^BJT: F391 WANfJlJ* D71 03 X3S93 
OC-KVLs F392 L (VOLTAGE (C 02 )> [4+0.6 [** 1.1909091 X3S9UI 
DC-KVH F393 [■ (VOLTAGE (C Q1H (4+ B.fi [A* 1.1983031 X369n I 
OC-KVLi F394 [- (VOLTAGE 1 02 fl3M (it fl.G (A* 1.1339091 X3G9))) 
OC-DHHi F33E (- (CJRPtNT Iffl ASM (4+ 1.44E-3 (ft* -i. 1303091E-4 X3S9HI 
OC-ZI-FU F33G (■ (CURRENT (S2 Ml) (4+ -l.ME-3 14* 1. 1309631 E-^ K3B91 1 J 
□C-KCLi F397 (. (CURRENT (C Q?l I 14+ l*WE-3 (4* -1.1989091E-4 K3G9m 

□C-KCL-BJTj F400 I- (CURRENT (E OEM (4* -1.44E-3 [4* U19B3991E-* X363t)) 

DC-KCLs F402 (- [CURflENT [01 R41 1 (4+ 1.44E-3 14* -1.1 903031 E-4 K3G9) H 
OC-OHIIi F4B3 1- [VQLTAtt fffl tall (*+ 2,532 (4* ~fl.2143&363G X3G9I)} 
Dt-KVL: F404 (. (VOLTAGE (E 021) (4* 2.592 (4* -e.2U363&3& X3€9)l> 
OC-BJT-ACTJVEi F40S (- (VOLTAGE (BG2T) (4+ 3 + 192 14* -fl,3l*363E3£ X3G3J 1 1 
YCB-MONlTOR-ajT: F40G (HANGING C7& 02 X3G9) 
VBE410NIT0R-BJTi F487 (HANGING 07 J 02 X3S31 

OC-KVLj F408 (- (VOLTAGE IE Oil I (4+3.132 (4* -8.214363&3G' H3G3) ) I 
DC -BJT -ACTIVE: F409 I- (VOLTAGE IB 01 M (A- 3.79C (4* -8,2143G3&36 X369111 
VCB-nOWtTOFl-BJT: F*L8 (HANGENG D70 01 X369] 
Vee-tlOHiTOfl-BjTL F4L1 (HANGING 071 01 X3B3) 

DC-lfVLt F412 (- IVOLtAGF. (ill R21I (*+ 3.732 [4* -8.2143E3&3G X369}]) 
DC-JCVLt F413 t- (VOLTAGE E*2 fill I t&+ 3.792 (4* -8.2143G3G3G X369))) 
OC-KVLt F41* (- TVOLTAGC CJS2 CC1 H i&t 3.732 (A* -0,2143G3E3G K3S3)H 
OC-DHIIi FH9 (- (CURflENT (ffl fill) (4+ 3.0291S92E-5 14* 5,73361 18E- 7 K3B3I » I 
OC-KCLl F^IS (- (CURflENT (ff2 U133H 

CA+ -5. 2L23GG3E-3 (4* -1.8^51675^^ X3G93 31 
DC-2T-SH0RT: F417 C- [CURRENT (#1 U1333 ' 

(** 5.2129Ee3E-3 (&* 1.44SI47S^E-^ X3G3>)t 
DC-CPROPi F41& f- [CURflENI [+VCC PRDT2}) 

(«*> 5,2l236B3E-3 S4* K&451&7E4E-4 X3S9)M 
DC-2T-Rt F419 (■ (CWRENT iKZ t\lt) (4+ -3.0291S32E-S 14* -5,793B118E-7 X36.9M1 
DC-Kat F420 (- iCUftREhJT (#1 R211 C4+ 3.0231S92E-S 14* 5h793G118E-7 X3G9> H 
DC-0HI1: F422 SCJ€CKE0 CHECK421 01 R2I 
DC- OHM: F423 1 VALUE «3S9 2 + S013641) 
DC-2T-H: F4Z4 1- tCURHENl (fl2 R2J f -3. 13H&94E-S) 

DC-2T-R: F&Z5 I- fCUHREAIT (tf2 R4J) -1.10G3B3E-3I 

DC-ZT-R: F4Z6 U 1CWRENT W2 fl?M -5.4&8932E-41 
OC-KCLe F427 (. ICUHRFWT {02 U14G)} S . 7293794 E -3 1 
DC-2T-5HGR7; F42S I- [CURRENT i#l U14S1 * -S.729E7B4E-3> 
DC-CPftOP: F423 {- (CURRENT [GROUND PROT?) h -5.729S784E-31 

Now all of the DC para mete; j of the circuit have been determined. At this time, EL 
btgiiii to pay jutmiiichi to the AC parameter*. It would be perfectly possible to deal with AC and 
DC analysis indiscriminately frrnn the beginning. bui is des-lrabl-e to do a; little worfc that will be 
forgotten dye to contradictions as :z possible, and therefore whatever Is likely to produce a 
■contradiction {such as DC analysis) ihouW rewive bighti priority than what will not produce one 
(such ai AC analysis), assuming that both will have lobe done in the end. 

INC-VRRDP: F430 [- [[NC-VCLTS 1*1 CCDl 0.11 
INC-CAP: F431 U tiNC-VQLTS (#2 CCtH $.11 
INC-KVL: F432 £- IIHC-YOLTS IE 01)1 0.1? 
I NO-KYI,: F433 [- (INC -VOLTS Ml fi?] I 0, |) 
INC-OL: F434 (- (INC-VQLTS 1*2 R1>J 8.11 
I NC-BJT -ACTIVE: FG35 [- [JNC-YOLTS IE D13> fl.ll 
iNC-KVLt F436 {- ttNC-VDLTS (6 U2r) 8,11 
J NC-BJT -ACTIVE: F*37 (- 1]«C-VDLTS IE Q2I1 0.11 
INC-KVL: F43S i~ (tNC-VDLTS iSl R4I) 0.U 
INC-CPHQP: F439 [- (flC-AFPS Ml U21«) I 0,0) 
INC-ZT-SHORT: F440 (- [[NC-W1PS MftlGHJ] a. 91 
[NC-VPROP: F441 [- [[NC -VOLTS {#1 11133)1 9.01 
Er*C-SH0RT: F442 {. 1 1 NC -VOLTS {#2 111331) 0,8) 
tWC-lfVL! F443 U nNC-VQLTS CC 04)) fl.fl) 
IWC-JCVLt F444 (. (INC-YDLfS fffl H12N fl.fi I 
ItJC-KVLi F445 t- (ENC-VOLTS 101 R&] > 0.9) 
IWC-KVL; F4*£ [. (iNC-VQLTS Ml Ftt) I 8,0) 
IrC-JCVL: F447 l- [INC-VDLTS tttl R13) 0.01 
JNC-OW* F44& {- (tNC-AIIPS itfl fill) -2.70Z70Z7E-71 
1NC-2T-R; F449 U 11NC-AP1PS (*2 Rl I } 2. 7B2?U27£-7) 
]NC-VpnaP: F450 (- (ENC-VDU& [JUL (J14SM 0.01 
INC-SHORT: F451 [- (ENC-VQlTS £*2 UH6H 0.01 
IMC-KVL3 F4S2 U * I NC-VOLTS (#2 fl&JI 8.0) 
trMC-KVLs F453 C- IIWC-VQLTS iJft"Z R13I1 0.01 
INC-KVL: F454 t- UKC-tfOLIS WZ CB-lt) 0.01 
INC-KVLt F45S [. (INC-VDUS C#2 R7J) 0.0) 
INC-KVL: F45E (. C[NC-V0Lf& C#3 R4)> 0.01 
]NC-KVLi F4&7 (- UNC-VOLTS M2 R2l> «,JJ| 
JNC-OHni F^53 U [JNC-ArP5 <tfl R2)l l.HE-El 
IMC-2T-H: FS53 (- IHC-AtlPS Ttf2 fl?l) -1.8E-G) 

JNC-GHrts F4S0 t- (INC-AHPS CJH 1 R4) I- 5.5555555E-51 
3NC-KCL: F4EI [- (INC-AHPS IE CIZ>) ^.5555555E-51 
]NC-27-fl* F4G2"U (INC-AffS (ff2B4>) -S.S5S5S5SE-5) 
INC -CAP t F463 (-. (INC-VOLTS (#1 CBD) fl-fl) 
INC-K'^t F4Gi (- (SNC^OLTS 1#Z AGN 0,3} 
INC-KVLs F*ES [- (INC-VOLTS \ft\ fl7h) 8 h 01 
1NC-OHM: F4GG C- (INC-W1P& (#1 R7) ) 3-3] 
)NC-2T-Rr F4G7 [. (INC-AHPS fJZ H7M fl.0) 
IWC-BJT-OJTOFF-IC: F4G9 (- ([NC-W1PS 1C 051] 0.0* 
TNC-KCL-BJT; F470 (. ([NC-AMPS IE Q&M 3.W 
INC-BJT-BETA-]NF[N]TE: F471 N fINC-AMPS (B 04h 8.B) 
tNC-BJT-BETA-]NF[N]TEi FtTZ (• (1NC-MFS (B 0(31) e>BI 
[ NC- B J T-BET A- INFINITE: F473 (- (jNC-AflPS <& 021) fl.0» 
INC-KCL: F474 (- (INC-AiFS (E QUI £.8) 
EHC-KCL-BJTt (=475 (- flJC-AflPS <C Q2l> S.5&555&SE-S> 
[MC-KCL: F^77 U (INC-AhPS («CCl)h -1.27027B27E-G* 
INC-2T-C: F47S (- f]WC-4HPS (#1 CC1I) 1,27M7827E-G) 
IMC-CPHOFl F47S (. (INC-AtlPS CIMPIPT PROT2J) K27027027E-6) 
INC-KCL-ejT: F4S8 r- [TNC-AAP5 (C QL1 \ 9<W 
INC-KCL; F4S1 (- EtNC-AHPS IK R3)l -5. &5K5S5E-5» 
]NC-2T-fi! F4&2 U ClNC-AfPS Ml A3}) 5. 56B5S5E-51 
)NC-0~: F4&2 L- (ENC-VQLTS m R31-I -0 . S&SKBS5J 
[NC-KVL:- F4S4 (- llNt-YQLTS (& 03) > -G.SSSSSSS&I 
IN--<V_: .-43b f- i:\f--Tirs IE Q71 I -3.S=15nF;=i!=5J 
I NC-flJT -ACTIVE: F4S7 I- (INC-V0US it OGf) -&.55S55SS5I 
INC-OHMs F4S9 U (1MC-AHPS (#1 RE) J -B.3iS342E-A) 
INC-KCL: F493 !- (1NC-AI1PS (E Q3M S.B13342E-4I 
IWC-KCL-BJT> F49L 1- tl NC-AMPS (C 03 M -S.aia3*2E-*) 
INC-2T-R: F492 (- t INC -AMPS EA2 R6I) B.3L-Bj42E-4> 
INC-KCL: F*53 1- UNC-AHPS m CB1)} -&,SlS3*2E-4} 
[NC-ZT-Cs F4S4 (- (]MC-AT1P5 [« C811 ) &.&1&342E-41 
GENVAHSi Fii97 1- [|NC -VOLTS (tfl R5) H H435f 
INC-KVL: F43B U [[NC-VDLT& CJHZ Rill) Xft3&) 
SNC-KVL: F4Bi: U tlNE-VDLTS (#2 R9) ) X435^ 
INC-KVL: F508 1- (INC-VOLIS (E Q5M X«9E) 
SNC-KVL? FS01 1- UNC-VOLTE ttft U2W \ H43St 
]NC-5HCRTj F&BZ (- DHC-VOLTS 1#1 LR141 ) X43SI 
lNC-VpfiOP; FEB3 (- ilMC-VOLTS IfUTPuT PR0J2I) K4S5> 

]NC-QHTIj F50i {„ [[IC-AMPS Iffl P.3U £** 4.54S454GE-4 K4S5M 
3NC-2T-R; F505 1- UWC-AllPS (#2 RfiS) \B» -4.^*546E-* X49GII 
CENVARS: F£0& 4- [TNC-VCLTS Ml R3M K53fi) 
3NC-KVL: FEBj 1- [TNC -VOLTS (B QB1 » K586 1 
INC-KVL: F613 I- f]NC -VOLTS ItH R10D X50G1 

INC-OHM: F51L U llMC-ATIPS l#l R9H El* (S* -1.9E-3 N43SJ 13* 1.0E-3 X&0GM I 
INC-KCL: F512 U OMC-W1P& (#1 R10N l*+ U* 1.9E-3 X49SS <&« -l,UE-3 ME0GJ I > 
[WC-DHM: F513 (- 1]WC-VflLTS {#2 HIS)) (4+ 14* -6.3 X4351 f«* 7.9 K5B6JM 
[MC-KVL: F$14 |- CINC-WQLTS Ml fllll) 1A+- 14* -5,8 X4351 f«* 7.6 X586))l 
[NC-tfVL: FS15 I- (IMC-TOLTS (E 04)1 lit 1A* -£.3 X435) 14* 7,8 X50g|]J 
INC-BJT-ACTEVEc F5I6 I- UNC-YQLTS (6 04) I [*+ («* -G.fi N4361 [4* 7,B K&BBm 
INC-KYU FBI 7 (- (INC- VOLTE it Q5J] <fi+ <&* -G.S H43SI 14* 7,8 K5B£>>) 
INC-ICVtE F518 !- UHC- VOLTS Itfl R13M (if «S* -E.8 X495J 14* 7*8 X50GD I 
IMC-KVl_: FG19 £- IINC-VQU5 Ctf2 R12I1 (if <4* -6.B X49SJ <4* 7,6 XS8GD I 
INC-KVL: F520 [- (INC-VPLTS <*Z CCZM 14+ <** -6.8 X4961 44* 7.8 XG8G3 II 
iNC-CAiPf FS21 [- ([NC-YOUS (ffl CCZN 14+ 14* -6.fi K495) IS* 7.8 X5G6I 1 1 
INC-KVL: FS22 £- UNC-VOUS (C 031 ] 14+ (** -6.fi X495I (4* 7.6 XS&GD > 
INC-KYL: F523 [- (ENC-VDUS tffZ R5D tit IS* -6,3 X4951 Ifi* 7,8 XS06DI 
INC-flKl: F524 {- EENC-ArFS (#1 R5)l 

[4+ (S* l r 2142fi&71C-3 X*3&] Ifi* -1. 3926571 5E-3 X50GDI 

(*+ <£* -1.214Z6&71E-3 X495) IS* 1.392A&71EE-3 K50G))) 
1NC-KCL: F526 U {1MC-AHPS (ffl CC2I) 

(*+ 6.318342E-4 fS* 1.2142S571E-3 K436h (J* -1.3S23571EE-3 M58GH ) 
INC-2T-C: FE-27 U nwC-ftPIPS r#2 CC2) * 

«fi+ -5.6U342E-4 <** -1.2K28571E-3 X496i {«* 1.39JSS71SE-3 X5ES&UI 
INC-OHHi F528 )- (IMT-AOPS (tfl R12M 14+ (S* l,743SS974E-4 X496I i&* -2.6E-4 M50&H j 
ENC-2T-R! P52S (^ UNC-AMPS {*2 ftl2J I [*+ Tit -l,7435S974£-4 K49S) (fet 2.0E-4 X5fi«»)] 
INC-KCL: f&ja (* r]NC-M1PS (#1 R131I 

ifi+ S.S1&342E-4 (J* 1.3336447E-3 K^3Sl IS* -1.59285713E-3 X&0E1)] 

E^JC-OHH: ^33 (VALUE X59G (i* 0.52242911 («* 9.37I7S43B X43&DI 
IHC-2T^R: F534 t- EENC-APPS \Wl R13IJ -4.96S3612E-5I 

IMC-KO.: F53S (- (INC-AHPS [« U146I] l£+ -7.7K3504E-4 [** 4.S4&i54GE 4 X49SM ) 
INC-2T-SH0RT: F536 (- CINC-AfFS m U14G) K (if- 7.7B5aM<iC-ft IS* -4,54S4&4EE-4 X49&HI 
IftC-CPROPi F537 U ntC-ftHPS ItnOl.Nn PR.1T2i> i&* 7.755SE.04E-4 IS* -4.E4$^54GE-4 H495M) 
INC-OWIi FS33 (- (ENC-AMPS \ft[ filDf Efi+ e.G6SK0GE-3 IS* -2-1276S356E-3 X43S)») 
INC-2T-R; F539 1- [1HC-AJ1PS (#2 RID J £4+ -^ , 6699S96E-3 IS* 2 f 127G595G£-3 X435)M 
INC-<CL: FE4H [- (ENC-ArFS 1ff2 H3> ) (4* 6.6SSabBEE-3 IS* -Z,5S2205E-3 X435] ) ) 
INC-27^R,' F542 l[>ECIfeQ CHECK541 D4 RSI 
3NC-2T-R] F543 (VsLUE X436 3.391&955I 
1NC-2T-R; FBA4 I- IIHC-aMFS [#Z RIB] I B.76H78SE-51 1 

tNC-KCLi F545 I- {1HC-AJ1P5 \EM\} -1.5AL5D334E-31 
tNC-KCL-BJTt FS4E f* UWC-ArlFS [C Q4)) 1.EUSS334E-4I 

ENC-KCL: FSM 4- tlWC-AnPS ltf2 ^1331 ) -7.G473795E-*} 
[NC-2T-SHQRT: F5&I I- (INC-AffS (ffl U133J> 7.G47379SE-4I 
ENC-CPPOP: FS43 (- iiNC-AhPS i+^CC P&0T2J f 7.G473795E-4I 




The anilysii u com-pkief We «n now a A far cite values of the quantities- of tn(c:csr eg us. The 
process of »iking replace; all symbolic "unknowns" of known value with chetr values, add perform; 
arithmetic operation-*, to make the answer more iranipjrtnt. tt also lists the factnames facts 
accessed in finding the answer 

--> (what '(vol lags (output aroi'2)]) 
7,3611562 CF3BS F2S7) 


m>> tuhat Minc-volta [output prot2) M 

3.3915055 (F543 F503) 


Since the input INC-VQLTS was .1. the output erf 34 indicate* a gain of" 31 for the circuit . 

Suppose that we. the circuit destgne.ri, ire unsaiisfied with the fain, as expressed by 
those results and would like m alter the circuit device para-meters to make thr gam -exactly 10. Wc 
can use EL to do this; first. we wnuid like to find out Which device paiameters can be used to 
vary the gain without changing the output bias level, and vice vera. 

"We use the fact that we can a.& ARS how n deduced any fact that it knows. UHV prints 
only the immedi.ire antecedents. EXPLAIN prints the entire proof, We Use them on tot tw u fads, 
F542 and F&03. which went into the ultimate answer for the gain toote lhat one is an expression 
involving: a symbolic unknown, and the other is, the value- of thai unknown^ presumably learned 
more recently than the expression itself ). «HV first describes the piven fact, then describes each of 
its immediate antecedent, one per tine. 

— * (why >f$431 

ANTECEDENTS QF F543 IYALUE X435 3,33150551 


FS33 (VALUE X5GG t*+ 0,52242011 («* 0.S71794&& W&m 


— > (why h fS33) 


F502 (- ([NC-VCLVS ^1 N2M>) H4S5I 


fZi? tlDENIIFY [fli U2t4) TEFintNALZlG) 



Unfortunately (but not surprisingly), ttw immediate antecedents of FS43 and r&@3 are 
still too high m the proof tree to include an* erf the initially-given device-paia meters we are 
looking for h so we must examine the enure proof. For each fact that appears in the proof, 
EXPLAIN prints the factname and then the statement of the fact, followed by the fad names oF ;he 
fact's antecedent. The arreted en Is' factnamrs may be interpreted by looking for them on Other 
lines of the printed proof, which is ordered numerical^ by. decreasing factnames,. The anlfcedent 
facts; will usually be accompanied! by the name of the demon which performed the deduction. 
GIVEN as an "antecedent" indicates, an assertion that was assumed, or given by the USer P rather than 
■deduced. USER as well indicates a fact Specified interactively by :he user with the TELL function. 

The only pans of the proof that we are actually Interested in are the facts that were 
"ajcjgms" specif ted when the circuit was wired up. They came near the end because (heir 
factrumei are all low-numbered. 

■■* (explain * fS*3l 

F543 (VALUE K435 j.o9150S51 (F&42 P533I 

F542 'CHECKED CHECKS^ D4 A91 (F&40 FS11 INC-2T-RI 

F54fi {. (INC-VIPS (#2 R91I 

(ft* 8,GG99SaGE-3 Ito -2.5S»fl5E-3 K4SHI) 
(FS33 F&94 F470 F449 HC-KCL) 
F539 (- (JNC-AHFS HEHIIJI (to -S« GS39&fiGt-3 (to 2.127G595&E-3 K435|lf (F533 WC~2T-Ri 
FS38 1- MNC-AHPS Ifll RUlf 

( ft+ 8 . 6G99G0GE -3 I St -2.12 7653&GE-3 X49&] f 1 
(F533 FBI 4 FiSS -l;? :«C-Qhn) 
F533 (VALUE KSflS [ft+ 0.S£2«S011 (to 8.8717348& X495l]l (F532) 
F&32 (CHECKEO CHECKG31 D3 fl:J3f [F&30 F^Lfi F453 F1ZS [NC-flHm 
F538 (- (INC-AMPS (#1 R131I 

(6+ S«818342E-4 (ft* 1.3aSG4*7^-3 X43SJ [ft* -1.592S&713E-3 X5K>n 
1F523 F527 F471 F4SS INC-KCLl 
FS23 I- 1]NC-AnPS ffl2 R123I 

(fi+ [to -l*7*35897*E-4 K496J (ft* 2,BE-4 K&BG})) 
iF523 i*JC-2T-RJ 
FS2S I- UNC-AHPS Ifll R121J 

1S+ (fi* 1 . 74358374E-4 X*35> 4 to -2, BE -4 K&8G) ) 1 
(F519 F4*4 F124 ENC-QHttl 
F527 (- (INC-AHPS (#2 CC23 ) 

(to -S.B18342E-4 (ft* -1. 21*2657 IE- 3 M9&) lA* l,39S&S71SE-3 KS86H) 
(FG26 1NC-2T-C1 
F52G L- llNC-ArPS (tfl CCZTJ 

(to 8.&183&2E-4 (to 1.2142S571E-3 X495t (A* -1.392B5715E-3 X£0Gm 
(FS25 F491 1NC-KOJ 
F&2S (- [iNC-AfTS [JCfl5)f 

(A* (ft* -1.2142S&71E-3 K495) l&e 1.3928S71SE-3 X5WJU 
(FS2* INC-2T-R) 
F&24 (- (INC-AhPS (#1 AS) > 

(to (ft* l,2U2aS71E-3 X495I [ft* -1.332B571&E-3 XSffill) 
(FS23 F445 F110 1NC-DHM* 

(IWC-VDLIS i.Wl H&M [<+ (ft* -6.8 X*9&] (ft* 7.S XS8G) ) \ (F&21 1NC-KVU 
(INC-VDLIS (#1 CC2>) (to (ft* -G.& K495J (ft* 7.6 *5BG)I> (FS2G INC-CAP) 
(IHC-VOLTS Of! CC2>) (to (ft* -G.B X49SJ (ft* 7.8 X£esm (Ffiie INC-fCVL) 
(INOVQL7S (JKZ H12>) (to «* -6,6X496) («* 7,8 K50G) t) IF51G 1NC-KVL) 

(itjc-vQuts wi nisn (a* [** -e.a xtgs) (to 7,s xsbgiit (FSis inc-kvli 

(INC-VOLTS (B 04) I (to- (ft* -6.fi X435) (ft* 7. a X50G))| iFSiS F274 INt-BJT-ftCTf VEI 

(1NC-V0LTS (E QU) (ft- (4* -6.8 X49S) (to 7,8 X&86)>) [FBI 3 [NC-KVU 
(3ND-V0LTS m RID) (4+ £«* -G.S Kft95) (to 7.8 X5Q6H1 (F513 1NC-KVL1 
(JNC-VQLTS (tf2 RlflU Lto (ft* -6.fi Kft951 (to 7.B KSe&n I (FEJ2 FSlfl F12fi 1NC-0HMJ 
(]NC-AMPS (#1 R18)) (to (to l.flE-3. X496J (ft* -1.9E-3 XE66] J I (FS11 F4G8 INC-<CL> 
(INC-AHPS (#1 H9») (fi+ (ft* -1.0E-3 W43S» (ft* 1.8E-3 XS@G>}) 

Fses F^gg fiis [nc-ohij 
(inc-volts (#1 Rian usas) (F&aa inc-kvli 

1] NC- VOLTS (#1 RS)) X&fiG> (CIVEH F327 F273 F278 F2G5 F2G2> 















































1 ] HC- 






















= <.7G 








■: i Mr 




F-i 7 7 


( ] NC- 




F -V ■ C 



















'. — 




n we- 



ll nc- 






t] NC- 



Cl NC- 































: '-:j.l: 


■; : NC 

AflPS [JH RSH I** ^.54G4E45E-^ X 435)1 IF437 F4SZ F116 lNC-OHPII 

VQLTB {#2 R9}5 ^951 *F497 ]«C-lfVL> 

VOLTS \Wl RID) K49S) (F437 IW^VU 


AMPS IC 031) -&<Sl&342E-4> CFA3fl F472 I HC-KCL -BJT f 

AMPS IE Q3D S.Bi83i3E-fc) (F«E9 INC-KCL) 

AMPS 1*1 R51) -S,B1&342-E-*) (F4B8 F4G4 FUZ [NC-OHMh 

VOLTS (tfl neit -8.55S555S5) IF4B7 1NC-KVU 


VOLTS IB 0313 -0.5S5B&5S*.) (F*B3 INC-KVLI 

VOLTS <«? R3D -0,S55SS5SS> (F48Z Fft4B F18G 1NC-0WM) 

■AMPS C#l R3H 5,S5S5S5SE-5> <F4Sl INC-2T-RI 

■AMPS (tf2 F3I) -5 f S55&5&$E-Sl 4F4SS F475 F47Z INC-KCD 

■AMPS <C 0111 Ol SF47S F474 lNC-KCL-BJD 


■AMPS IC QZ>J 3.35SS5S«E.-6h LF473 F4G1 1NC-KCL-B-IT J 

■AMPS IE Ql>] e.Sl IF473 1NC-KCL} 


(F271 ir£>BJr-BErA-!MF[NtTE) 

{F274 [MC-Bjr-BETA-IWFfNlTEl 


[F3Z& iNC-eJl-CUIOFF-lCl 

VDLIS Etfl CB1D 0h9> IF454 JtC-CAPI 
AMP5 LB] RAJ h 5.5SS5S55E-SS (FiSE F43S F16S [NC-DHnt 
VOLTS (Jffi R4H B.8) IF451 INC-Kvp 
VOLTS (#2 CB1D 0»B» (F45t INC-KVL1 
VOLTS Wl ft!3D fl.BJ (F451 INC-UVL1 
■VOLTS <B2 RB)) 8,0} (F4S1 [fC-KVL> 
■VQLTS (#2 U14&D %.%\ [F4S5 [MC^SHORT) 
■VOLTS Wl W146D B,B> CF2Z9 trJC-VFflDPJ 
■VOLTS m R3J) 0.0> IF44S ENC-KVL) 
■VOLTS ffll RSI) 0.et [F442 :NC-KVL) 
■VOLTS (Ml H12)> 9.B> IF«2 lHC-KVLy 
VOLTS <fl2 W133D fl r 0) CF44'i PNC-SHDHTl 
■VOLTS [J01 U133M B-BJ (F2-38 tNC-VPROP) 
■AI1PS i«2 UZ14D B-9> CF433 LfJC-2T -SHORT 1 
AMPS (#1 IC141J 9.B) (F23L 1NC-CPRQPI 
■VOLTS Wl R4H B.11 IF437 1NC-CTL1 
■V0LT3 [F- Q23 1 B.11 {F43G FZEG I NC-&JT -ACTIVE) 
■VOLTS (B 02 D 8*1) iF43S IfC-KVLl 

■jMIFS IB 02M 3.81 

•AriFS IB 03 D 0.81 

ft"P£ IB 34 M 8,81 

M^S {E QSiih 0.8t 

VPS (C Q5D 8,01 

AtTPS [B DSD 0,0h 

F^3S im (INC-VOLTS IE Qlf> BU) (F432 F263 INC-&JT-ACrEVE^ 

F432 (- (INC-VQLTS (B QlM 0,1] 1F431 1SC-KVL* 

F431 (- UNC-vOLTS Iff? CtllV MJ (F430 ]NC-CAP> 

F438 f- UNC-VOLTS (#1 DGH> &.1) (F232 ]JC-VFR0Ph 













F£$3 (NEEDCH01CE (MK)E 03 I) (Tfty-SJTI 




F231 U (INC -AMPS (WTPtJT PR0T21 » 8,01 (USER GIVEN I 

F238 (- (|NC -VOLTS (*VCC PRQT2M «»ffl (USER GIVEN) 



F124 (- (RESISTANCE A12> 39308,8) (GIVEN) 

F122 <- (RESISTANCE fill ) 470,81 CGI VE1NI 

FL28 [- (RES [STANCE fUGt &6QQ<0} (GIVEN' 

F11S I. (RESISTANCE A3) 1003. fil (GIVEN) 

Fllh t- (RESISTANCE RSI 2200. B) (GlYENI 


F110 (- (RESISTANCE H5) 5&00.BI (GIVEN) 

F18S (- (RESISTANCE ft*l 1&03.BI (GIVEN) 

F10E L (RESISTANCE 03) 10030.01 IGIY£N> 



Wi> see (h&i the precise resiinnces of resistors R&, R4, R5, R6 r R6, R9, Rio, Rtl. RL? and 
R]5 had an effect on the derivation of Oct F&43, Changing (tie resistance of any of [hr other 
ceitstors {R], R% R?) wjll leave F$^3 s-till true, This «r> be understood by examining (he path 
along which F5G3 was deducra 
«> (explain H (£B3] 


FBB2 (« (1NC-V0LTS (tfl 14214)1 M435) (F561 ] hC-SHDFl T l> 

FS01 <- 1 INC -VOLTS C«K2l4)r X4SS> LF«J7 LNC-liVLI 

F497 1- (INC-VOLTS (ffl RS) r N49&i (GIVEN F327 F273 F279 F265 F2£Z1 






F261 (r^EOCHOICE CnODE 01 It (TRt-BjT) 

F2G0 (rJEEOCHOICE C(10D£ 02) i URY-BJT) 



F2S7 (WEEQtHOJpE (lluOE QSl ) (TRY-BJTl 



Since F&02: depends cm no additional lesistartce Y allies, ihe Ciretm gam I (self depends 
only on R3, R4, R5, R6. R&. R9 R1C, Rll. RL2. and R]J To change the gain to 40, we cotild pick 
one of [hem and Uf different values For it until we found one producing a Satisfactory value fqr 
the gain. But there is an easier way! Wc can give one of the resistors a tvtiaWt value, »nd tet it 
be determined in terms, of the desired gain. FJtje we tell the system no forget the value it already 
knows, for one of the relevant resistors (R5); then we give it a new value winch 1.5 a symbolic 
unknown (RRSK 

[11 addition, we know itoi if we change the reiistance. of one of (he cite? resisfprs, Rl, R'." 
or R7, the dram's gun win not t>e affected its (ong ai we don't change the resistance 50 much that 
the transistors move to different opeiatmg regions! But if that happens, we will sre it). We can 
thus us* then* resistors to adjust other thing-s about the circuit, afwf aiming at the desned g*in. 

■ ■> (change '(resistance r51 \ 
468 facta to check out 
3S2 active facts I a ft 

The value of Rb*s resistance ts now "forgotten" (actually merely disbelieved.), and scj is 
everything that was deduced frorVit. The information that is left when RS's resistance is gOTe is: 



— > (tell ' [rstiitar-ies H53 Yr5J 

Mow we mull pr-opagatr the newly trailed unknown, ARE. This means determining the valnei of 
the circuit volrcig« and currents at cxprtititMS involving rtarr unAFrtwir. 

«> (run! 

OC-0HT1: F5B1 {- (VOLTAGE 1*2 R5H *&*■ 1S.B «* -S^B£3S?E-<t HR5>)> 

OC4<VU F552 (. (vQLT*GE Wl CCZ)l 14+ »S.fl l£* -8.*am2E^ RFi^m 

OC-KVL; F553 £- VOLTAGE 1C Q3] I [$+ IS. «S* -8.4«g9&ZE-4 AHSm 



INC^T-R; F5SS U (1NC-AHPS {$Z R9>ll (** C«* l,GE-3 M9-SI 

INC-OHni FSSS t- [[NC-AHPS lAj R131) (*+ [«* -S^92&83E-5 

1NC-2T-Rs F557 I- [LNt-ArPS (ff2 H131 1 l&^ IS* S.292SB3E-5 

]NC-0*1: F55S [. CNC-AMF^ «1 Rl 1 > J 

t&* 1.&* -0,3i6&9&7^£ K49S) (** 0.016&g&74^ X&B6J Sf 

16* -l,0E-3 X50Sm 

M35) 1«* 9<512135E-5 XSe&M) 

MRS) l«* -9,51SLS5E-5 X&aSm 


INC-2T-R: FSfil t- <lNC-AhPS t#2 fiiflJ} (&+ 14* -1.0E-9 X4353 <4* l.BE-3 XS&&I 1 1 

ENC-KCL: FES2 4- {]NC-tf1PS (E 04 M 

{4+ 14* B.017S9S7W.mG X4-9SI (4* -8. 81 759574 44& XS06M) 

(4* (4* -0. 81 759574 WG X495) {4* 0k J 75967ft 44E XS0&I11 
INC-ZT-Rl .F564 <- HKC-AMPS \M2 KID) 

14+ (4* 0,8185957445 Xt&l (4* ~M1EG9£7M€ XttGII) 
INC-KCLi F5G5 f- UNC-H1P5 (*2 Wi45] > 

{*+ -8>25Z7S65E-4 <£* 3.7161BG3W-* M35I *&* 9.S1219EE-5 X50G> I P 
]NC-2T-SH0RTt FSBe I- ([IC-AHFS (Jf| UltSM 

<4* fi.2S27a6BE-4 14* -3.71618G26E-4 K49&J (4* -S>51Z195E-5 tiS0GI>) 

(4+ &,2&27SGSE-4 (ft* -3.71G1S62BE-4 *495J («* -3, SUISSE -S XfcBG) M 

IS* («* 2,57ZSSS84£'4 X49&> IS* ^2>351Z135E-4 XE06] II 

£4+ 14* -2.S72S5S84£-<h M9&> (it 2.9512195E-4 X50G) M 
INC-KOLe F570 (- IINC-AMPS !ff2 ASM 

<4+ S.SJS3*2E-4 (4* 2.S728S884E-4 K49SI 14* -2»3&l2195E-4 X5WH 1 
INC-2T-R: FS71 l- CtNC-ArPE Iffl R5JP 

(4+ -*.fiie342E->4 (** -2,&72S5804E-4 M95P 1** 2.3S12L95C-4 MEEEH ) 
IHC-KCL: F572 S- 1HC-AMRS [fl2 W13313 

IS* 8>2&5*8922E-4 [4* 9.917678B713 IW36) !4* -^.0175905665 XSB6) ) > 
INC-ZT^EHORTj F&73 {- IINC-AITS i*l W133M 

[4+ -3,Z£S48822E-4 

<fi* -0,01767^713 K49S) 
14* 0.017G90BGG& X50E1I) 
1NC-CPRDP; FS74 [- (LNC-AflPS (+VCC PR0T21 1 

(*+ -&,2GSi8922t-<t 14- -0,017G7$&713 X49&J (** 0,817G90&&&5 X5GGU 1 
IHC-QHIli F577 (VALUE RR5 \%tf ii* {4* 6-8 M9&J 14* -7*8 «50G) I 

*&♦ -8.813^::e-s 

is* -;.&7z8esme-4 x495> 
{&•: 2.ssi2iasE-4 xseei»}) 

VCB-M0N17DR-BJT: FE7fi (HANGING O?0 03 X&0&1 
[WC-KFJL; F5S2 (VALUE XE-8G («* 1.82S8327 K49&] J 

The value of RflS, and thui of R5'i rDiistance. is Vnown only in terms of anothEr 

unknown, K49S H became, with on? lesi quantity %ivm than before, there is no longer trough 
Information to determine all the circuit paramencrs. We can remedy that by specifying the OUlpttt 
iignal level a* 4-0 volts, which is a gain of 1TJ over rhe input wr have supplied 

«> (toll 'line-volte [our^t prot2)'l b T &t 

LrSffiE F&&S f- ([NC-VQLIS {OUTPUT PH0T2] J 4,0) 


■■> (runt 

VCa-firJNSTOH-BJTi F5£6 {VALUE X495 4,8) 

INC-VPfiOPt F5&S lOfCkED CHECKSa? 044 TERr1]IML216> 


The appropriate Value of R&'s resistance is now known, 

--> [what ' treai atance r"5l ) 

6SS5 + 7402 (F&&2 F£8G FS?7 FG&BJ 


«> [uhst T flnc-vo!t5 CS2 rS)f) 

4.ea&3S fFSSZ F58S F523) 


--> [what MvoHage <tf2 rgM) 

3.171GSS45 IF&8Z F556 FS77 F&51f 


--> tuhat T (vol tags (sqJJIl 

3.33S17 FF433 F3SS> 


--> [what ' linc-volta to q3* ) } 

-fl.GSfcSS&SE SF4Js7l 


Hue, by changing the Value Of R6 (O gel the right gain, we have aljo altered the hi as me, of Tin* 
circuit. We now adjust the tuns (Q (he desired level by changing R7 t which EL hai told us au^f nff 
affect the gam. 

--» (change ' (real glance r-7) ) 

417 facts to check, out 

351 active tacts loft 


*-> fuhat + Treiiitanct r5) ii 

5965*74^2 fF&&2 FSSS F577 F5&9) 


--> [uhat " (voltage (c q31 ) ) 


■■> Crur) 














-21 -R 

: F533 


—> (tell * (vol lege lc q3>) 9.51 
USER: F5S9 (- (VOLTAGE 1C Q3) I 9,5] 


( VOLT AGE IJTl CC2M 9.5) 

(VOLTAGE iffZ R5> » 9<5T 

(CURRENT 1ft REh) S.0107&SG3E-4) 
. (CURRENT (ftfZ R5J h -8.0107?,3G3E-41 
DC-KCL: FS94 (- (CURRENT 1C Q3) I &.0107G963E-4! 
DC-KCL-BJTt F53& t- {CURRENT IE Q3> I -8>ei07S3E3E-4> 
DC-KCLi F59G t- tCUnflEUT [01 RG)> 3<S10753G3E-4> 
PC-PHHi FE-9? U (VOLTAGE (#i RSI > (A* , 56^ . r L : 7*. X3E9) !■ 
OC-KvL: F59& {» (VOLTAGE tE O0M (** 8. 50467374 1<363>) 
□G-BJI-ACTlVEt FE-93 I- [VOLTAGE (6 03)1 (4+ 1.1ME797S X3GSI I 
VCB-TQWiTQR-BJT: F398 (HANGING 070 03 X36a> 
V0E-nONnOfi-BJT: F331 (HANGING 071 03 K3G9I 
DC-KVL: F&flfl U (VOLTAGE (C 02] I («+ i. 18*67975 X3G5)) 
X-KVL: FS31 (- (VDLTAGE IC Pll I £4+ 1. 10*67975 H35"9] I 
DC-KVL; FGG2 (- [VOL FACE Iff 2 R3)} 14* 1.1841*7975 X^&g) I 
DC-OHM : FB03 C- (CURRENT Ml R3)> {4+ 1 . 3&353203E-3 (4* -l.BE-4 X3&9HI 
DC-2T-P,: FEB* (» (CURRENT (ffZ H3»J (4+ -1.339&3203E-3 (4* K0E-4 X369m 
DC-KCL: FG0E [. (CURRENT (C 02 M (4+ 1.389S3283E-3 (4* -K8E-4 H3G9D1 
IC-nOMtlOR-BJT: F338 (HANGING DS& 02 X3S3] 

DC-ICCL-ajT: FG8G (- (CURRENT fE 023 > 14* -J..3£953283E-3 (4« l + 8E-4 X3&9>n 
tE-llDhllTflft-BJT: F481 (HANGING D6S Q2 X3G9> 

DC-KCL: F687 (- {CURRENT ffll tt4H (4+ l,38953283E-3 (4* -l-BE-4 X369) 1 1 
OC-QHrt: F68fi (* [VOLTAGE 1*1 H4M (4* 2.5&1157G* I**-?. 18 1*3691] I 
OC-KVL: F6B9 (- (VOLTAGE IE Q2>l (*f 2.501157&4 (4* -8>1& M369H3 
DC-BJT-ACTIVEl FS18 (- [VOLTAGE IB 02) f {4*3,101157^* (4* -fi.lfi X363J ) ) 
VCQ-dONtrOR-flJTj F40& (HANGING D70 02 X3G91 
VBE-rWHtTOR-BJIi F48? (HANGING D71 02 X353f 

DC-KVLf F611 (- (VOLTAGE IE QUI 1**3.19115764 [«* -fl.l* X3G9) II 
DC-BJT-ACirVEl FE12 S- (VOLTAGE (8 Oil) l«+ 3.78J1&7& l#v -8.1* X3G9I>> 
VC^-nDNITOR-BJl: F*18 (HANGING 078 01 X3e9k 
VBE^nDNnCFl-BJT: Fill {HANGING 071 01 %m> 

DC-KVL: fG13 I* (VOLTAGE (ffl R2I) (fit- 3.70I1E7E («* -0,1B K3591 ) I 
DC-KVL: FG14 |. (VDLTACE (#2 AIM l&t- 3.70H&7G (** -9, IS K3S9B1 
DC-KVL: F61S (^ {VOLTAGE W2 CCM S [*+ 3.7811S76 14* -8.18 X3633IJ 
OC-OHM: F5I6 (- rcUflREHT \#l RID (4f 3.8&37412E-5 (4* 4 + 8S4B64SE-7 K363> 1 1 
DC-KCLl FB17 (- iCURflENT Lrf2 U133S} (4^ -5.3e3S228E-3 (4* 9.35135i3E-& 5<3S3>>> 
0C-2T-SH0RT: FEia l» 1CURHENT (#1 U1331J (4+ SH3B3822gE"3 (** -S f 3S13513E-5 H369) 5 1 
OC-CPnOP: FG19 I- (CURRENT (+VCC FflOT2>) (*+ S.9G3BZ2HE-3 (4-* -9, 951 351 3£ -5 X3€9J 3> 

DC-2T-flt F620 [. i CURRENT (S2 fill? «+ ^0&374i2E-£ (A* -«>$548G48E-7 X3G9) ) ) 

DC-KCL: FS21 I- !CtflRENT 1*1 R21) i$+ 3,fl537412E-S C«* 4.fi£«6B*5E-7 X3G3) ) ) 


DC-QHH* FG24 (VALUE X3G3 2. 831490371 

□C-21-Rj F424 [- (CURRENT (62 R2] I -3.13H&94E-SI 

DC-27-Rj F4C!: I- (OF^ENl (02 Ril ! 1 . 10G3ftJt£-L: I 

0C-2T-H) F625 (- (CURRENT (JS2 RE] t -S,ei078SS3E-4|- 

OC-KCL: FE2E [. (CURRENT Ml (17) ) a.0107&3E>3E-4) 

DC-OHM: FE27 {. (RES E STANCE R7) 3S34.S9S3] 

DC-2T-R: FE2B (- {CURRENT [ffZ R7I} -£,8lB7ag63£-41 

DC-KCL: FE23 (» (CURRENT (#2 U14G1 J £.GS20512E-3r 

DC-2T-SHDRT: FE3B (- (CURRENT (jS; PKG!- ' -S.£42iaSl2E~3l 


IMC-DHH: F46G (- UNC-AHPS (#1 R7] K G.B) 

Unout: F4S3 (. WNC-AMPS Wl CB1) t -A.M&342E-41 

Uncut: F4S4 (- ([NC-AMPS 1*2 CB1 J I S.RJO^-4) 

Unoutt F4G7 (- (INC-AMPS «2 A7») 8,01 

Unoutt F5G5 I- ([NC-AH B S 1*2 ui 461] 

(4+ -S.2S27S5E.E-i [6a 3-7LeiSG2&£-4 K435J {«* 3.51219&E-G X50SI )] 

Unoutt FSGG (- (INC-AhPS Iff! U1461) 

14+ B,25273&E-4 (4* -3.71618G26E-4 *49S) «* -S.S12195E-5 X58£)l) 

Unoutt F5G7 [- (ENC-AhPS IISOUHG] FR0T2J I 

(4* 8,2E27£G£E-4 <G* -3. 716J.8S2SE-4 ^43^] f«* -3,S12135E-5 X506IH 

Now we have determined the value of R7 thai >ve need 1o get the deiired operating point 
The amplifier'* d«i£n is now complete; after asking for lh* component Values we have just 
determined, we ire ready 10 build the- circuit 3nd ■verify our result!. 

--i (mhat * ires i g i ance r&t] 

GfiGS.7402 {F5S? FB3C F377 F550I 


■■■> [what * (resi stance r?i \ 

353*, SSW JFG27) 


--> Lnhat ^voUsflt U C[3JI) 

3.3361701 (FEE* FES?] 


--> (uhat * tine-volt* to q3U) 

-e.$SSS$535 1F*37) 


Blind alleys 

Various other systems Invp h?*-n investigated which try to maVe effective u*e of the 
results of blind alleys, Including; 

BUILD *Fahlman I973>. TOPLE <McDermctH IStf-h, HACKER <5ussman l*73.1S75> 


One way to prevent combinatorial explosions ij to formulate one's domain so that (here 
is l Finite St! of "slots' CO be filled. Nc^ins.' geometry theorem prover *Nevins 197+^ makrs. ujt of 
thii property of geometry problems without constructions. "Although the program does re* use a 
diagram directly, It does take advantage of the manageable problem space implicit in the diagram. 
An important aspect of human problem solving may be the ability to structure a problem space » 
that forward chaining tech n i ouej enn be m?$ effectively." The Ffl AME system? approach of 
Minsk y *M insky 39*7H> and Wlnograd ^Winograd 1971 > shares this essential finiteness at the dala 


One of the major limllations on the development -of large ekpen programs is the 
complexity barrier encountered *hen the program gets so large that It I* hard to Keep the 
interactions between its parts under control Various sohtllons to thi$ prohlem have bppn nffpred. 
The "structured programming" movement *t5ljl(stra lsY70> proposes to constrain the style of 
programmers SO that the interactions are clarified and limited. Others *Tertelman T9T0> 
<Winograd i^y propose to build ^sterns which supply wronger support to programmers in term* 
of rcrtJtinr bookkeeping. The eKlremeform of this idea leads to vanous "automatic programming" 
efforts These range from "programming apprentices" <Hewitt St Smith 1975*. <Rich &■ Shrubr 
\$7§> to ejqiert system compilers ^AUTOPROG \ r j7b> and various automatic synthesis systems 
^StiJiman 19^,1975* -rSussmari IWv Another approach is to Cry to constrain the representation of 
knowledge in a program ro be as simple and modular as possible. This has led to various attempts 
to build "rule based" systems and "idvLce takers" su<h as MYCIN -:Shortliffe I974> rDavjj J97£> 
and EL NASL ^McDcrmott 19^6^ is a computer programming language Which attempts to 
provide feature* for organizing programs alohg ihtsc Hnes. 


In the MYCIN jysfem sShertliffe L971> ^Davis J976> the ability to generate coherent 
explanations of Its reasoning plays an important ^at't In the debugging of the rule set and in the 
acceptance of its conclusions by its users. 


The AFS program 13 implemented in MACLISP ^Moon I^H\ a version of LISP 

-^McCarthy l*J66>. which wai created and Is u*ed at the MIT Artifirta* Intelligence Laboratory and 
MIT Project MAC LISP has been the language of many targe and Interesting programs became 
Of its elegance, simplicity* and convenience for symbolic manipulation. MACLISP Is available Oft 

the MULTlnS, TOPS-LCi. and the JncnmruHble Timesharing systems. 


Antecedent Reasoning Syitom 

Pattern-directed invocation 

Pattern^ iretted invocation ^Hewitt W\> ii ati artificial inrerHgence programming 
technique whereby a program can be executed without knowing its name. There are I wo fcttms of 
partern-dkeoted cnvocarron, 111 one tind. A roirtrnedefinlilon Specifics a pattern *hich "advertises" 
the kLnd or problem the romine is useful for The routine can then be invoked by a special kind 
or call which specifies a pattern describing the problem to be solved. This kind of pattcrn-dJrefreri 
invocation may be used to implement consequenl reasoning. ]n the kJnd we use, a "demon" 
program may be defined with a pattern which Spcdfiej that tt JhouU be invcifcrd whenever an 
event matching tha( pattern occut.5 This kind of demon is ltseTijI for fflOfiHorlng an indexed data 
base. It may be awakened by any change in the data base notching tts pattern of invocation. 
Thii kind of pattern-directed invocation may be usFd to l^pkment antecedent reasoning. 

Data Base* 

An Important feature of most M languages (eg. Planner '-Hewitt I972>, Micro Plan net 
«5ujsman r Winograd & CharniaV |?"70>, ConnivEi *McDc1n>DlC & Simman I9?2>, f^M <Rulifson 
l9tt£>) ii the indexed data base. It is ohen important io be able tn record a "fact" in so that it can 
be accessed in many; ways, For example, we may want to record the information that Bl is a big 
red block so Chat rf later a program wants (o know i^hat binds a T <- red or ir there a?e ftnj- big red 
Objects, the intern can retrieve rhat Information even though the awetrlng process does not know 
V* hat. questions are going to be asked. The indexed data base is fundamentally a fuKy inverted f He 
or records of variable length. Efficient means of impleowriting such structures are still a matter of 
research interest fMcDermott W&*, 


TOPLE <rVfcDermott I9?4> was an early a'.'.empt in lecord the interactions among 
deductiqni for the purpose of deciding what \i current^ believed to be true. McBermott used this 
Information to help decide which of several assumptions must be thrown out in order to keep a 
consistent data base when a new fact conflicted with existing ones. MYCIN <&h«rlhf fe 1974? 
<Davis 19?$j use dependency Information to produce explanaUons but do not use it fot any control 
purposei, The SRI Computer Based Consultant <Flkei Wtb> makes use of dependencies to 
determine the toxical support of facts in a manner jJmlbir to ARS but does not use them to control 


A preview* version of EL which *ai much more JirlmiCJfc than the one we describe 
here, wai implemented directly in LtSP tSussman & Stallmsn r9TC>, 


AnMysu by propagation of constraints Li alio Impltmrn^d In INTER <de Kleer 19>B>. 
A similar proce-is of relaxation of symbolic constTalnii hu been applied to the libelling of ^ine 
drawing S of Visual scenes d-luFrman L970:-. A beautiful exposition of This technique can be Found 
In <Wa1tt Iff72>. Some theoretical analysis of this technique appear* In «Freurler 197S>. 

Symbolic manipulation 

Much mote powerful and extensive symbolic algebraic manipufallon systems have been 
written than the one we use In E1_. The moil power Ful one we know of Is MACSVM A 
<JtfACSYMA 1974.:- 


In a real design Situation, the designer knowsthe intended operating point region of the 

devices, in question. The USeT of EL may, of OOUrW, supply any in f ormallOU whirb F.L could 
deduce as p Arivke h to The system If a contradiction occurs due To his advice, be .rfimild hr very 


Chronological backtrack control was implemented in Micro-Planner ^Sussman. Wmograd 
St Chamiak iSttb. Uwrs of Micro-Plahner ^Te plagued by scriotti ptoblems ^Sussmah &■ 
MtDermett 19^>. The control of the eombmatOTial searclms performed by Micro- Planner is neaily 
Impossibte due to The large number of anomalous dependencies (in AHS term*) Introduce by th« 
chronologkal component of ihe hacktTack JtKfc- 


This, measure of simultaneity wis proposed by Louii tJ. Braida. 


A Llerh'n'ion of this interesting behavior can be found tn ^Senturla * Wedlock I97^> pp. 



NA5L ^McDermcit! I9"?&.> Is implemented with a similar queuelest scheme for interpreting 

rules. This scheme is very elegant and flexible, 


List* which arc EQUAL In the LISP ^nsp have the same properties^ so Inter lisp's 
<iNTEHLt5P I974i hash-link? would nol fill the bitt. 

Discrimination nels 

The decision tree merbnd oF implementing a pattern dat^-hase For demons is Similar to 
The Kbeme used in QAi <Rulifson 19>T2>. 



Bosyj. Michael Adi agnatfic prog ra m for the dciigri of prtuwranm isgtgmj MTT Project 
MAC Technical Report *f:j (July I97i) 

?Davls I976> 

Davk, Randall Application of meta frvri knowledge to [he contraction, maint enance, 
and use of large knowltdgpbajw Sranfarrt U. Al Ub. Memo AlM-Zffl (July I9>7&) 

<de Klwr I97&* 

de Kkrr r Johan Loral Mr hpt h for Local nation of Faulti m Electronic Circuits MIT A I 
Lab. Working Paper 109 (September 1076} 

<Dijkstra 19TO> 

Dijkstra. Ed*g*r W. "Structured Programming" in ggft^irt engineering tec h n Iquri, 
J.N.Buxton A- B Randc1l(Eds.} NATO Scientific AUnm Division. BtusipIi, Belgrupi. 1^0. 81-fiS. 

<Doyle t97fl> 

Doyle. Jot "Analysis by Propagation of Constraints In Elementary Cmm«ry Problem 
Solving" MIT Al Lab. Working Paper 108 (April 1*76) 

<Fahlman I973> 

Fahlman, Scott Elliot A Planning SyHivn for Robot Construction Task;. MIT Dept. of 
EESfCS MS Thesis. MIT Al Lab Technical Report ?M {May lift?) 

-*FiJt« I975> 

FikM, Richard E. PftJucllMf Retrieval Mechani sm* for State Prempt loh Modcb 
Stanford Research Institute Al Technical Note hTG (July I975> 

■^Fteuder 1970> 

Freijder, Eilgertc C. Synch winne C ons traint Exprmions MIT Al Lab. Mfmo J70 ( 1 uly 

<Hewittlc Smith t97S> 

Hewilt, Carl E. & Smith, Brian "Toward? a Programming Apprentice" in IEEE Trans. 

Off Software Engineering Val.l Nol pp.2&-45 (March 197^) 

■cHtwltt 197| > 

Hewitt, Carl E. "Procedural Embedding of Knrjwfedge In PLANNER" in Proc. IICAI 1 
(Sep ler-bcr 1971) 

<Hewin I97?> 

Hewitt, Carl E. pesHlptlori and Theoretical Analysis (U.^ing Schemata) of PLAM NER:_A 

Language for Prnvtng Thftorpms .^nd Manipulating Models in a Robert MIT Al Lab. Technical 
Report ?58 (April 197?) 

^Huffman I97Q> 

Huffman, David A-- "Impassible- Objects as Nan sense Sentence" In Machine Intetiigencf 
6 Edinburgh, U.K.; Edinburgh University Pren (1970) 

«INTERL1£P 1974?- 

T*ttelman> Warren rt a I FNTERLI SP Refer ence Manual XEROX Palo Alio Research 
Center and Bolt Beranek and Newman (1974) 


Bogerx Richard rt ah MACSVMA Rel errntt_Manua1 MIT Project MAC (September 

<Maiort !&"?&n 

Mason, MalThew T. QuahatlvcSlriwtatlon or Swine Production MIT Dppt. dF EE&CS 
BS Tlieiis (May 19%) 

■^McCarthy I965> 

McCarthy rt al. LIS P_ 1.5 ?TOErarnrner H s. Manual Cambridge Man: MT.T, Press (1965) 

<McD*mvHt * SuHfrtan IS'FS* 

McDermott,. Drew VtrKent and Sussman, tleiald Jay CONN TVER Reference Manual 
' MIT A I Lab. A I Memo 259 (Mjy 1972, reviied jury BUS) 

<McD*rmDtt 197-1 > 

McDermott. Drew Vincent Assimilation of New information by a Natural Language 
Understanding System MIT Dept, of EEfrCS MS Thesis, MIT Al Lab Technical Report 291 
(February 197*) 

<McDermatE I9fl5> 

McEfermott, Drew Vincent Very Large Planner-type Data Bases MIT AT Lab. Me*no 339 


< McDermott I97&> 

McDermott. Dtew Vincent Flexibility and Efficiency in a Computer Program for 
Designing Circuits MIT Dept. EEfrCS PhD Thesis {September I07&) 

* M Inst y i9T4> 

Minsky. Marvin Lee 'A Framework for Representing Knowledge*' MIT A I Lab Memo 

90S (June 19**), in The F mholo pr y of Computer Vision P. H Winston McCraw-Hill 0975) 

<Moon 197l> 

Moon, David A, MACLISP Reference Manual HtT Project MAC (April! 19*4 J 

<Nc vim 19*1 > 

Ne^ins. Arthur J. Plane CeomeUr Theorem Proving UsJne Fo r ward Chaini ng, MIT 

Art Kick? I Intelligence Memo 303 (J&nnairy 1*74} 

cHkh it Shrobe 19*6> 

Rkh. Charles * Shrobe. Howie Initial Report on a LISP Programmers Apprentice MIT 

At Lab. Technical Report tti (Sent. 1976) 

cRoylancc 1975^ 

RoyUnrr, CeralO Uifael Anthropomorphic Cucun Analysis MTT T>ppt. ol Er>CS B^ 

Thesis (June 1975) 

<Roylance I97&> 

Roylancc, G«abd LaFael Qualitative A nal gia of Operational AmpHf let Circuits MIT 

Dept. oF EE&C5 MS Th«is ptopoial (March 19*6) 

cRulirson t972> 

Rulifson. John* F. et al. A procedural catailM for imuitrte reasoning Stanford Research 

Institute AI Technical Mote 73 {November 19?£3 

Venturis * Wedlock 19?5> 

Sentoria, Stephen D. and Wedlock, Btuh D Election It Circuits and Applications New 

York: John Wiley and Sans (ISTB) 

■cShortlirff 1974> 

Short hf fe_ EJH. MYCIN - A rule-tan-d ccrnptlKr program for advising ph ysicians 
regarding antLmkrablal therapy selection Stanford U. AT Lao Memo AIM -251 (October 19*1). also 
MYCIN: Co m puter- Based Mescal Consultations, New York; Ebevler W) 

tSuiifwn & McDermnlt 197?* 

Sustnun, Gerald Jay and McDtmwt Drew Vincent "From PL AM HER. to CONNIVER 
-- A getietfc approach" In Pra. F |GC (19*2) pp. 1171-1119 


^Sussman 8c Stallman 1975> 

Suisman, Gerald jay and Stallman. Richard Maltha "Heuristic Techniques in 
Computer- Aided Circuit Analyst*" in IEEE Trans on Circuits andjystgms vol. CA5-22 No. II 
(November 1975) 

^Sussman E973j97-5> 

Suiiman, C-eraM lay A Computer Model or 5ki» AojuisirJsn MIT De P r of Maih PhD 
Theilj (Aclguit ]9ft). also New VorV: ElKtkr (1*75} 

■rSusEman [-97-j> 

Suufflarr. Gerald jay The Virtuous Naiure or Bu^' In Proc, oftheAJSB conference 
Suiiex, UK fjulf 197*) 

■rSuisinan, Wino^rad & Charniak 1470.* 

Susimar,, Gerald >y. Wirrngrad, Terrv, and Charniak, Eugene Mkr o-Flar.ner Rgfcrmre 
Manual MIT Al Lab. At Memo 201 {Jul/ I970 r revved Dtcembpr 1971) 

<TrJie.lman I970> 

TeitePman, Warren, Toward a Programming Laboratory - in Software engineer I ri p 
techniques. j.N.Busmn fc BRaodeH(Eds.) NATO Scientific Affairs Div, S ion, Brum*. Belpium 
l$7fl h 137-149 H 

<Waltj 1972* 

Waltt, t} 4 vJd L. Generat ing Seniwnttc Descnp it oiu from Dra fringe of Scenes wiih 
Shadows MIT AS Ub. Technical R Sport 27( (November 197?) 

<Wir>ograd t973> 

Winofrad, Tfflry "fire^ing the Complicity Barrier AfJtrr H In Free. ACM 
BIGFN/SIGIR Interface M Vrtinjr (November 1973) 

cWtaognd I97*> 

Wlnograd, Terry Tram* Repressions ind th* PioceduraVDecla^tlve Controversy" in 
RtpKMrtation & Undemanding. D G.lobrow * A.Cdlirn (Eds.) N«w Ywk: Academk Prcii (197.',)